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

Result code in 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>
Result on the web
<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>

Result language
angličtina
Original language name
Testing Isomorphism of Chordal Graphs of Bounded Leafage is Fixed Parameter Tractable
Original language description
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.
Czech name
—
Czech description
—

Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project
<a href="/en/project/GA20-15576S" target="_blank" >GA20-15576S: Graph Covers: Symmetries and Complexity</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2022
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)