DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2020.4

Isomorphism Problem for S_d-Graphs

Authors: Deniz Ağaoğlu and Petr Hliněný

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract

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.

Cite as

Deniz Ağaoğlu and Petr Hliněný. Isomorphism Problem for S_d-Graphs. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 4:1-4:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{agaoglu_et_al:LIPIcs.MFCS.2020.4,
  author =	{A\u{g}ao\u{g}lu, Deniz and Hlin\v{e}n\'{y}, Petr},
  title =	{{Isomorphism Problem for S\underlined-Graphs}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{4:1--4:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.4},
  URN =		{urn:nbn:de:0030-drops-126754},
  doi =		{10.4230/LIPIcs.MFCS.2020.4},
  annote =	{Keywords: intersection graph, isomorphism testing, interval graph, H-graph}
}

Search Results

Documents authored by Ağaoğlu, Deniz

Isomorphism Problem for S_d-Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message