Primal-dual approximation algorithms for feedback problems in planar graphs

DOI10.1007/PL00009810zbMath0928.90094OpenAlexW4244206605MaRDI QIDQ1307344

David P. Williamson, Michel X. Goemans

Publication date: 31 October 1999

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/pl00009810

zbMATH Keywords

planar graphsfeedback problems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (14)

Edge-disjoint odd cycles in 4-edge-connected graphs ⋮ Hitting Weighted Even Cycles in Planar Graphs ⋮ Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms ⋮ Approximate min-max relations for odd cycles in planar graphs ⋮ Outerspatial 2-complexes: extending the class of outerplanar graphs to three dimensions ⋮ A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem ⋮ A primal-dual approximation algorithm for the vertex cover \(P^3\) problem ⋮ Primal-Dual Approximation Algorithms for Node-Weighted Steiner Forest on Planar Graphs ⋮ Planar graph bipartization in linear time ⋮ Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms ⋮ The ferry cover problem ⋮ Feedback arc number and feedback vertex number of Cartesian product of directed cycles ⋮ Maximum Weighted Induced Bipartite Subgraphs and Acyclic Subgraphs of Planar Cubic Graphs ⋮ An improved approximation bound for minimum weight dominating set on graphs of bounded arboricity

This page was built for publication: Primal-dual approximation algorithms for feedback problems in planar graphs