2010 | OriginalPaper | Buchkapitel
Isomorphism for Graphs of Bounded Feedback Vertex Set Number
verfasst von : Stefan Kratsch, Pascal Schweitzer
Erschienen in: Algorithm Theory - SWAT 2010
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
This paper presents an
${\mathcal O}(n^2)$
algorithm for deciding isomorphism of graphs that have bounded feedback vertex set number. This number is defined as the minimum number of vertex deletions required to obtain a forest. Our result implies that
Graph Isomorphism
is fixed-parameter tractable with respect to the feedback vertex set number. Central to the algorithm is a new technique consisting of an application of reduction rules that produce an isomorphism-invariant outcome, interleaved with the creation of increasingly large partial isomorphisms.