Primo Search

# Fast Minor Testing in Planar Graphs

## Adler, Isolde ; Dorn, Frederic ; Fomin, Fedor ; Sau, Ignasi ; Thilikos, Dimitrios

Algorithmica, 2012, Vol.64(1), pp.69-84 [Periódico revisado por pares]

Texto completo disponível

• Título:
Fast Minor Testing in Planar Graphs
• Autor: Adler, Isolde ; Dorn, Frederic ; Fomin, Fedor ; Sau, Ignasi ; Thilikos, Dimitrios
• Assuntos: Graph minors ; Planar graphs ; Branchwidth ; Parameterized complexity ; Dynamic programming
• É parte de: Algorithmica, 2012, Vol.64(1), pp.69-84
• Descrição: Minor Containment is a fundamental problem in Algorithmic Graph Theory used as a subroutine in numerous graph algorithms. A model of a graph H in a graph G is a set of disjoint connected subgraphs of G indexed by the vertices of H , such that if { u , v } is an edge of H , then there is an edge of G between components C u and C v . A graph H is a minor of G if G contains a model of H as a subgraph. We give an algorithm that, given a planar n -vertex graph G and an h -vertex graph H , either finds in time $\mathcal{O}(2^{\mathcal{O}(h)} \cdot n +n^{2}\cdot\log n)$ a model of H in G , or correctly concludes that G does not contain H as a minor. Our algorithm is the first single-exponential algorithm for this problem and improves all previous minor testing algorithms in planar graphs. Our technique is based on a novel approach called partially embedded dynamic programming .
• Idioma: Inglês