On H-Topological Intersection Graphs

Kód výsledku v 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>

Nalezeny alternativní kódy

RIV/00216208:11320/17:10368818

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

On H-Topological Intersection Graphs

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

On H-Topological Intersection Graphs

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2017

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE (WG 2017)

ISBN

978-3-319-68705-6

ISSN

0302-9743

e-ISSN

1611-3349

Počet stran výsledku

13

Strana od-do

167-179

Název nakladatele

SPRINGER INTERNATIONAL PUBLISHING AG

Místo vydání

CHAM

Místo konání akce

Heeze

Datum konání akce

21. 6. 2017

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000440865800013