Primal-dual approximation algorithms for feedback problems in planar graphs
From MaRDI portal
Publication:4645920
DOI10.1007/3-540-61310-2_12zbMath1415.90101OpenAlexW2091757422MaRDI QIDQ4645920
Michel X. Goemans, David P. Williamson
Publication date: 11 January 2019
Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-61310-2_12
approximation algorithmplanar graphlinear programming relaxationundirected graphnetwork design problem
Integer programming (90C10) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Related Items
A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs ⋮ Feedback arc set problem and NP-hardness of minimum recurrent configuration problem of chip-firing game on directed graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Maximum induced forests of planar graphs
- On acyclic colorings of planar graphs
- Approximating minimum feedback sets and multicuts in directed graphs
- An approximate max-flow min-cut relation for undirected multicommodity flow, with applications
- Packing directed circuits fractionally
- A primal-dual approximation algorithm for generalized Steiner network problems
- Vertex packings: Structural properties and algorithms
- Approximating Minimum Subset Feedback Sets in Undirected Graphs with Applications
- A General Approximation Technique for Constrained Forest Problems
- When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
- Approximate max-flow min-(multi)cut theorems and their applications
- Node-and edge-deletion NP-complete problems
This page was built for publication: Primal-dual approximation algorithms for feedback problems in planar graphs
