Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/978-3-642-13731-0_9 | SWAT |
Keywords | Field | DocType |
fixed-parameter tractable,feedback vertex set number,isomorphism-invariant outcome,minimum number,mathcal o,graph isomorphism,bounded feedback vertex set,large partial isomorphisms,vertex deletion,new technique,feedback vertex set | Discrete mathematics,Combinatorics,Graph isomorphism,Vertex (graph theory),Neighbourhood (graph theory),Cycle graph,Vertex cover,Feedback vertex set,Feedback arc set,Mathematics,Maximal independent set | Conference |
Volume | ISSN | ISBN |
6139 | 0302-9743 | 3-642-13730-X |
Citations | PageRank | References |
20 | 0.79 | 26 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stefan Kratsch | 1 | 561 | 42.59 |
| Pascal Schweitzer | 2 | 214 | 16.94 |