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%3A10368818" target="_blank" >RIV/00216208:11320/17:10368818 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/00216208:11320/17:10439053

Výsledek na webu

<a href="https://link.springer.com/chapter/10.1007/978-3-319-68705-6_13" target="_blank" >https://link.springer.com/chapter/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

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 Open image in new window -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(n4)-time algorithm for recognizing K1,d-graphs. For the dominating set problem (parameterized by the size of H), we give Open image in new window - and Open image in new window -time algorithms on K1,d-graphs and H-graphs, respectively. Our dominating set algorithm for H-graphs also provides Open image in new window -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

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 Open image in new window -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(n4)-time algorithm for recognizing K1,d-graphs. For the dominating set problem (parameterized by the size of H), we give Open image in new window - and Open image in new window -time algorithms on K1,d-graphs and H-graphs, respectively. Our dominating set algorithm for H-graphs also provides Open image in new window -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

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

ISBN

978-3-319-68705-6

ISSN

0302-9743

e-ISSN

neuvedeno

Počet stran výsledku

13

Strana od-do

167-179

Název nakladatele

Springer International Publishing

Místo vydání

Neuveden

Místo konání akce

Nizozemsko

Datum konání akce

21. 7. 2017

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

WRD - Celosvětová akce

Kód UT WoS článku

—