Primal-dual approximation algorithms for feedback problems in planar graphs

DOI10.1007/3-540-61310-2_12MaRDI QIDQ4645920zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

approximation algorithmlinear programming relaxationnetwork design problemplanar graphundirected graph

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Primal-dual approximation algorithms for feedback problems in planar graphs
• A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
• scientific article; zbMATH DE number 139781
• Approximating minimum feedback sets and multi-cuts in directed graphs (extended summary)
• Primal-dual approximation algorithms for node-weighted Steiner forest on planar graphs

Cites work

• A General Approximation Technique for Constrained Forest Problems
• A primal-dual approximation algorithm for generalized Steiner network problems
• An approximate max-flow min-cut relation for undirected multicommodity flow, with applications
• Approximate max-flow min-(multi)cut theorems and their applications
• Approximating minimum feedback sets and multicuts in directed graphs
• Approximating Minimum Subset Feedback Sets in Undirected Graphs with Applications
• Approximation algorithms for NP-hard problems.
• Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs
• scientific article; zbMATH DE number 1003266 (Why is no real title available?)
• scientific article; zbMATH DE number 139781 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1263259 (Why is no real title available?)
• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• Maximum induced forests of planar graphs
• Node-and edge-deletion NP-complete problems
• On acyclic colorings of planar graphs
• Packing directed circuits fractionally
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Vertex packings: Structural properties and algorithms
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks

Cited in

(7)

• A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
• Primal-dual approximation algorithms for feedback problems in planar graphs
• Feedback arc set problem and NP-hardness of minimum recurrent configuration problem of chip-firing game on directed graphs
• Primal-dual approximation algorithms for node-weighted network design in planar graphs
• scientific article; zbMATH DE number 1526336 (Why is no real title available?)
• Hitting weighted even cycles in planar graphs
• Approximability of the independent feedback vertex set problem for bipartite graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4645920)