Contraction Bidimensionality: The Accurate Picture

DOI10.1007/978-3-642-04128-0_63zbMath1256.05202OpenAlexW121113946WikidataQ60488676 ScholiaQ60488676MaRDI QIDQ3639283

Dimitrios M. Thilikos, Fedor V. Fomin, Petr A. Golovach

Publication date: 29 October 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2010/2500/

zbMATH Keywords

contraction containmentcontraction-closed parametersgraphs of large tyreewidth

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (14)

A Retrospective on (Meta) Kernelization ⋮ Contraction bidimensionality of geometric intersection graphs ⋮ Planar disjoint-paths completion ⋮ Unnamed Item ⋮ Harmless sets in sparse classes ⋮ 1-perfectly orientable \(K_4\)-minor-free and outerplanar graphs ⋮ On graph contractions and induced minors ⋮ Subexponential algorithms for partial cover problems ⋮ FPT approximation and subexponential algorithms for covering few or many edges ⋮ Induced minor free graphs: isomorphism and clique-width ⋮ Confronting intractability via parameters ⋮ Spanners in sparse graphs ⋮ Contraction obstructions for treewidth ⋮ Contraction-Bidimensionality of Geometric Intersection Graphs

This page was built for publication: Contraction Bidimensionality: The Accurate Picture