AGAOGLU, Deniz and Petr HLINĚNÝ. Isomorphism Problem for Sd-Graphs. In Javier Esparza and Daniel Kral. 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fur Informatik, 2020. p. "4:1"-"4:14", 14 pp. ISBN 978-3-95977-159-7. doi:10.4230/LIPIcs.MFCS.2020.4.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name Isomorphism Problem for Sd-Graphs
Authors AGAOGLU, Deniz (792 Turkey, belonging to the institution) and Petr HLINĚNÝ (203 Czech Republic, guarantor, belonging to the institution).
Edition Dagstuhl, Germany, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), p. "4:1"-"4:14", 14 pp. 2020.
Publisher Schloss Dagstuhl - Leibniz-Zentrum fur Informatik
Other information
Original language English
Type of outcome Proceedings paper
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher Germany
Confidentiality degree is not subject to a state or trade secret
Publication form electronic version available online
RIV identification code RIV/00216224:14330/20:00114291
Organization unit Faculty of Informatics
ISBN 978-3-95977-159-7
ISSN 1868-8969
Doi http://dx.doi.org/10.4230/LIPIcs.MFCS.2020.4
Keywords in English intersection graph; isomorphism testing; interval graph; H-graph
Tags core_A, firank_A, formela-conference
Tags International impact, Reviewed
Changed by Changed by: prof. RNDr. Petr Hliněný, Ph.D., učo 168881. Changed: 14/4/2021 22:16.
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.
Links
GA20-04567S, research and development projectName: Struktura efektivně řešitelných případů těžkých algoritmických problémů na grafech
Investor: Czech Science Foundation
MUNI/A/1050/2019, interní kód MUName: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace IX (Acronym: SV-FI MAV IX)
Investor: Masaryk University, Category A
MUNI/A/1076/2019, interní kód MUName: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 20 (Acronym: SKOMU)
Investor: Masaryk University, Category A
PrintDisplayed: 21/5/2022 15:35