Anzeige
Erschienen in:
2017 | OriginalPaper | Buchkapitel
On H-Topological Intersection Graphs
verfasst von : Steven Chaplick, Martin Töpfer, Jan Voborník, Peter Zeman
Erschienen in: Graph-Theoretic Concepts in Computer Science
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Biró, Hujter, and Tuza introduced the concept of H-graphs (1992), intersection graphs of connected subgraphs of a subdivision of a graph H. They naturally generalize many important classes of graphs, e.g., interval graphs and circular-arc graphs. Our paper is the first study of the recognition and dominating set problems of this large collection of intersection classes of graphs.
We negatively answer the question of Biró, Hujter, and Tuza who asked whether H-graphs can be recognized in polynomial time, for a fixed graph H. Namely, we show that recognizing H-graphs is
-complete if H contains the diamond graph as a minor. On the other hand, for each tree T, we give a polynomial-time algorithm for recognizing T-graphs and an \(\mathcal {O}(n^4)\)-time algorithm for recognizing \(K_{1,d}\)-graphs. For the dominating set problem (parameterized by the size of H), we give
- and
-time algorithms on \(K_{1,d}\)-graphs and H-graphs, respectively. Our dominating set algorithm for H-graphs also provides
-time algorithms for the independent set and independent dominating set problems on H-graphs.
-complete if H contains the diamond graph as a minor. On the other hand, for each tree T, we give a polynomial-time algorithm for recognizing T-graphs and an \(\mathcal {O}(n^4)\)-time algorithm for recognizing \(K_{1,d}\)-graphs. For the dominating set problem (parameterized by the size of H), we give
- and
-time algorithms on \(K_{1,d}\)-graphs and H-graphs, respectively. Our dominating set algorithm for H-graphs also provides
-time algorithms for the independent set and independent dominating set problems on H-graphs.