Other formats:
BibTeX
LaTeX
RIS
@inproceedings{1848138, author = {Agaoglu Cagirici, Deniz and Hliněný, Petr}, address = {Cham}, booktitle = {WALCOM: Algorithms and Computation}, doi = {http://dx.doi.org/10.1007/978-3-030-96731-4_20}, edition = {LNCS 13174}, editor = {Mutzel, P., Rahman, M.S., Slamin}, keywords = {chordal graph · H-graph · leafage · graph isomorphism · parameterized complexity}, howpublished = {tištěná verze "print"}, language = {eng}, location = {Cham}, isbn = {978-3-030-96730-7}, pages = {239-250}, publisher = {Springer, Cham}, title = {Isomorphism Testing for T-graphs in FPT}, year = {2022} }
TY - JOUR ID - 1848138 AU - Agaoglu Cagirici, Deniz - Hliněný, Petr PY - 2022 TI - Isomorphism Testing for T-graphs in FPT PB - Springer, Cham CY - Cham SN - 9783030967307 KW - chordal graph · H-graph · leafage · graph isomorphism · parameterized complexity N2 - 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]. ER -
AGAOGLU CAGIRICI, Deniz and Petr HLINĚNÝ. Isomorphism Testing for T-graphs in FPT. In Mutzel, P., Rahman, M.S., Slamin. \textit{WALCOM: Algorithms and Computation}. LNCS 13174. Cham: Springer, Cham, 2022, p.~239-250. ISBN~978-3-030-96730-7. Available from: https://dx.doi.org/10.1007/978-3-030-96731-4\_{}20.
|