Testing Isomorphism of Chordal Graphs of Bounded Leafage is Fixed Parameter Tractable

Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F22%3A43966101" target="_blank" >RIV/49777513:23520/22:43966101 - isvavai.cz</a>
Výsledek na webu
<a href="https://www.springer.com/series/558" target="_blank" >https://www.springer.com/series/558</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-031-15914-5_3" target="_blank" >10.1007/978-3-031-15914-5_3</a>

Jazyk výsledku
angličtina
Název v původním jazyce
Testing Isomorphism of Chordal Graphs of Bounded Leafage is Fixed Parameter Tractable
Popis výsledku v původním jazyce
The computational complexity of the graph isomorphism problem is considered to be a major open problem in theoretical computer science. It is known that testing isomorphism of chordal graphs is polynomial-time equivalent to the general graph isomorphism problem. Every chordal graph can be represented as the intersection graph of some subtrees of a representing tree, and the leafage of a chordal graph is defined to be the minimum number of leaves in a representing tree for it. We prove that chordal graph isomorphism is fixed parameter tractable with leafage as parameter.
Název v anglickém jazyce
Testing Isomorphism of Chordal Graphs of Bounded Leafage is Fixed Parameter Tractable
Popis výsledku anglicky
The computational complexity of the graph isomorphism problem is considered to be a major open problem in theoretical computer science. It is known that testing isomorphism of chordal graphs is polynomial-time equivalent to the general graph isomorphism problem. Every chordal graph can be represented as the intersection graph of some subtrees of a representing tree, and the leafage of a chordal graph is defined to be the minimum number of leaves in a representing tree for it. We prove that chordal graph isomorphism is fixed parameter tractable with leafage as parameter.

Druh
D - Stať ve sborníku
CEP obor
—
OECD FORD obor
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt
<a href="/cs/project/GA20-15576S" target="_blank" >GA20-15576S: Nakrývání grafů: Symetrie a složitost</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění
2022
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Podobné výsledky(10)