Isomorphism Testing for T-graphs in FPT

AGAOGLU CAGIRICI, Deniz a Petr HLINĚNÝ. Isomorphism Testing for T-graphs in FPT. In Mutzel, P., Rahman, M.S., Slamin. WALCOM: Algorithms and Computation. LNCS 13174. Cham: Springer, Cham, 2022, s. 239-250. ISBN 978-3-030-96730-7. Dostupné z: https://dx.doi.org/10.1007/978-3-030-96731-4_20.

Základní údaje

Originální název

Isomorphism Testing for T-graphs in FPT

Autoři

AGAOGLU CAGIRICI, Deniz (792 Turecko, domácí) a Petr HLINĚNÝ (203 Česká republika, garant, domácí)

Vydání

LNCS 13174. Cham, WALCOM: Algorithms and Computation, od s. 239-250, 12 s. 2022

Nakladatel

Springer, Cham

---

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10200 1.2 Computer and information sciences

Stát vydavatele

Švýcarsko

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

tištěná verze "print"

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14330/22:00125687

Organizační jednotka

Fakulta informatiky

ISBN

978-3-030-96730-7

ISSN

DOI

http://dx.doi.org/10.1007/978-3-030-96731-4_20

Klíčová slova anglicky

chordal graph · H-graph · leafage · graph isomorphism · parameterized complexity

Štítky

core_B, firank_B, formela-conference

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

A T-graph (a special case of a chordal graph) is the intersection graph of connected subtrees of a suitable subdivision of a fixed tree T. We deal with the isomorphism problem for T-graphs which is GI-complete in general – when T is a part of the input and even a star. We prove that the T-graph isomorphism problem is in FPT when T is the fixed parameter of the problem. This can equivalently be stated that isomorphism is in FPT for chordal graphs of (so-called) bounded leafage. While the recognition problem for T-graphs is not known to be in FPT wrt. T, we do not need a T-representation to be given (a promise is enough). To obtain the result, we combine a suitable isomorphisminvariant decomposition of T-graphs with the classical tower-of-groups algorithm of Babai, and reuse some of the ideas of our isomorphism algorithm for Sd-graphs [MFCS 2020].

---

Návaznosti

GA20-04567S, projekt VaV	Název: Struktura efektivně řešitelných případů těžkých algoritmických problémů na grafech Investor: Grantová agentura ČR, Structure of tractable instances of hard algorithmic problems on graphs
MUNI/A/1145/2021, interní kód MU	Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace XI. (Akronym: SV-FI MAV XI.) Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace XI.