Isomorphism Problem for Sd-Graphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F20%3A00114291" target="_blank" >RIV/00216224:14330/20:00114291 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.4230/LIPIcs.MFCS.2020.4" target="_blank" >http://dx.doi.org/10.4230/LIPIcs.MFCS.2020.4</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.MFCS.2020.4" target="_blank" >10.4230/LIPIcs.MFCS.2020.4</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Isomorphism Problem for Sd-Graphs

Popis výsledku v původním jazyce

An H-graph is the intersection graph of connected subgraphs of a suitable subdivision of a fixed graph H, introduced by Biró, Hujter and Tuza (1992). We focus on S_d-graphs as a special case generalizing interval graphs. A graph G is an S_d-graph iff it is the intersection graph of connected subgraphs of a subdivision of a star S_d with d rays. We give an FPT algorithm to solve the isomorphism problem for S_d-graphs with the parameter d. This solves an open problem of Chaplick, Töpfer, Voborník and Zeman (2016). In the course of our proof, we also show that the isomorphism problem of S_d-graphs is computationally at least as hard as the isomorphism problem of posets of bounded width.

Název v anglickém jazyce

Isomorphism Problem for Sd-Graphs

Popis výsledku anglicky

An H-graph is the intersection graph of connected subgraphs of a suitable subdivision of a fixed graph H, introduced by Biró, Hujter and Tuza (1992). We focus on S_d-graphs as a special case generalizing interval graphs. A graph G is an S_d-graph iff it is the intersection graph of connected subgraphs of a subdivision of a star S_d with d rays. We give an FPT algorithm to solve the isomorphism problem for S_d-graphs with the parameter d. This solves an open problem of Chaplick, Töpfer, Voborník and Zeman (2016). In the course of our proof, we also show that the isomorphism problem of S_d-graphs is computationally at least as hard as the isomorphism problem of posets of bounded width.

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

<a href="/cs/project/GA20-04567S" target="_blank" >GA20-04567S: Struktura efektivně řešitelných případů těžkých algoritmických problémů na grafech</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2020

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

45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

ISBN

9783959771597

ISSN

1868-8969

e-ISSN

—

Počet stran výsledku

14

Strana od-do

„4:1“-„4:14“

Název nakladatele

Schloss Dagstuhl - Leibniz-Zentrum fur Informatik

Místo vydání

Dagstuhl, Germany

Místo konání akce

Praha

Datum konání akce

24. 8. 2020

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

WRD - Celosvětová akce

Kód UT WoS článku

—