Planar Branch Decompositions I: The Ratcatcher

DOI10.1287/ijoc.1040.0075zbMath1239.05176OpenAlexW2151721933MaRDI QIDQ2892257

Illya V. Hicks

Publication date: 18 June 2012

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/867af9d95fc97d9defc4be708f00bc8b8f1c5d6d

zbMATH Keywords

algorithmplanar graphplanar hypergraphsbranchwidthcycle methodcarving widthoptimal branch decomposition

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (10)

On the minimum corridor connection problem and other generalized geometric problems ⋮ New analysis and computational study for the planar connected dominating set problem ⋮ Practical algorithms for branch-decompositions of planar graphs ⋮ Branch decomposition heuristics for linear matroids ⋮ Treewidth lower bounds with brambles ⋮ Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs ⋮ Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs ⋮ Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms ⋮ Treewidth computations. II. Lower bounds ⋮ A Local Search Algorithm for Branchwidth

Uses Software

• TSPLIB

This page was built for publication: Planar Branch Decompositions I: The Ratcatcher