D 2020

Isomorphism Problem for Sd-Graphs

AGAOGLU, Deniz a Petr HLINĚNÝ

Základní údaje

Originální název

Isomorphism Problem for Sd-Graphs

Autoři

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

Vydání

Dagstuhl, Germany, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), od s. "4:1"-"4:14", 14 s. 2020

Nakladatel

Schloss Dagstuhl - Leibniz-Zentrum fur Informatik

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

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

Forma vydání

elektronická verze "online"

Kód RIV

RIV/00216224:14330/20:00114291

Organizační jednotka

Fakulta informatiky

ISBN

978-3-95977-159-7

ISSN

DOI

Klíčová slova anglicky

intersection graph; isomorphism testing; interval graph; H-graph

Štítky

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 14. 4. 2021 22:16, prof. RNDr. Petr Hliněný, Ph.D.

Anotace

V originále

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.

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/1050/2019, interní kód MU
Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace IX (Akronym: SV-FI MAV IX)
Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace IX, DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty
MUNI/A/1076/2019, interní kód MU
Název: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 20 (Akronym: SKOMU)
Investor: Masarykova univerzita, Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 20, DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty