Fast Minor Testing in Planar Graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Article Dans Une Revue Algorithmica Année : 2012

Fast Minor Testing in Planar Graphs

Résumé

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 $\cO(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 {\sl 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 \emph{partially embedded dynamic programming
Fichier principal
Vignette du fichier
Minor-planar.pdf (386.26 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-00904515 , version 1 (16-09-2019)

Identifiants

Citer

Isolde Adler, Frederic Dorn, Fedor V. Fomin, Ignasi Sau, Dimitrios M. Thilikos. Fast Minor Testing in Planar Graphs. Algorithmica, 2012, 64 (1), pp.69-84. ⟨10.1007/s00453-011-9563-9⟩. ⟨lirmm-00904515⟩
537 Consultations
147 Téléchargements

Altmetric

Partager

More