Efficient Isomorphism for Sd-Graphs and T-Graphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F23%3A00130021" target="_blank" >RIV/00216224:14330/23:00130021 - isvavai.cz</a>

Výsledek na webu

<a href="http://arxiv.org/abs/1907.01495" target="_blank" >http://arxiv.org/abs/1907.01495</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00453-022-01033-8" target="_blank" >10.1007/s00453-022-01033-8</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Efficient Isomorphism for Sd-Graphs and T-Graphs

Popis výsledku v původním jazyce

An H-graph is one representable as the intersection graph of connected subgraphs of a suitable subdivision of a fixed graph H, introduced by Biró et al. (Discrete Mathematics 100:267–279, 1992). An H-graph is proper if the representing subgraphs of H can be chosen incomparable by the inclusion. In this paper, we focus on the isomorphism problem for Sd-graphs and T-graphs, where Sd is the star with d rays and T is an arbitrary fixed tree. Answering an open problem of Chaplick et al. (2016, personal communication), we provide an FPT-time algorithm for testing isomorphism and computing the automorphism group of Sd-graphs when parameterized by d, which involves the classical group-computing machinery by Furst et al. (in Proceedings of 11th southeastern conference on combinatorics, graph theory, and computing, congressum numerantium 3, 1980). We also show that the isomorphism problem of Sd-graphs is at least as hard as the isomorphism problem of posets of bounded width, for which no efficient combinatorial-only algorithm is known to date. Then we extend our approach to an XP-time algorithm for isomorphism of T-graphs when parameterized by the size of T. Lastly, we contribute an FPT-time combinatorial algorithm for isomorphism testing in the special case of proper Sd- and T-graphs.

Název v anglickém jazyce

Efficient Isomorphism for Sd-Graphs and T-Graphs

Popis výsledku anglicky

An H-graph is one representable as the intersection graph of connected subgraphs of a suitable subdivision of a fixed graph H, introduced by Biró et al. (Discrete Mathematics 100:267–279, 1992). An H-graph is proper if the representing subgraphs of H can be chosen incomparable by the inclusion. In this paper, we focus on the isomorphism problem for Sd-graphs and T-graphs, where Sd is the star with d rays and T is an arbitrary fixed tree. Answering an open problem of Chaplick et al. (2016, personal communication), we provide an FPT-time algorithm for testing isomorphism and computing the automorphism group of Sd-graphs when parameterized by d, which involves the classical group-computing machinery by Furst et al. (in Proceedings of 11th southeastern conference on combinatorics, graph theory, and computing, congressum numerantium 3, 1980). We also show that the isomorphism problem of Sd-graphs is at least as hard as the isomorphism problem of posets of bounded width, for which no efficient combinatorial-only algorithm is known to date. Then we extend our approach to an XP-time algorithm for isomorphism of T-graphs when parameterized by the size of T. Lastly, we contribute an FPT-time combinatorial algorithm for isomorphism testing in the special case of proper Sd- and T-graphs.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10200 - Computer and information sciences

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í

2023

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 periodika

ALGORITHMICA

ISSN

0178-4617

e-ISSN

1432-0541

Svazek periodika

85

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

32

Strana od-do

352-383

Kód UT WoS článku

000850021200002

EID výsledku v databázi Scopus

2-s2.0-85137458099