On H-Topological Intersection Graphs
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F17%3A10439053" target="_blank" >RIV/00216208:11320/17:10439053 - isvavai.cz</a>
Alternative codes found
RIV/00216208:11320/17:10368818
Result on the web
<a href="https://doi.org/10.1007/978-3-319-68705-6_13" target="_blank" >https://doi.org/10.1007/978-3-319-68705-6_13</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-319-68705-6_13" target="_blank" >10.1007/978-3-319-68705-6_13</a>
Alternative languages
Result language
angličtina
Original language name
On H-Topological Intersection Graphs
Original language description
Biro, 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 Biro, 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 NP-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 O(n(4))-time algorithm for recognizing K-1,K-d-graphs. For the dominating set problem (parameterized by the size of H), we give FPT- and XP-time algorithms on K-1, d-graphs and H-graphs, respectively. Our dominating set algorithm for H-graphs also provides XP-time algorithms for the independent set and independent dominating set problems on H-graphs.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
—
Continuities
S - Specificky vyzkum na vysokych skolach<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2017
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE (WG 2017)
ISBN
978-3-319-68705-6
ISSN
0302-9743
e-ISSN
1611-3349
Number of pages
13
Pages from-to
167-179
Publisher name
SPRINGER INTERNATIONAL PUBLISHING AG
Place of publication
CHAM
Event location
Heeze
Event date
Jun 21, 2017
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000440865800013