A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
From MaRDI portal
Publication:1273087
DOI10.1016/S0167-6377(98)00021-2zbMath0920.90137MaRDI QIDQ1273087
Michel X. Goemans, Dorit S. Hochbaum, David P. Williamson, Fabián A. Chudak
Publication date: 23 September 1999
Published in: Operations Research Letters (Search for Journal in Brave)
combinatorial optimizationnetwork designundirected graphsfeedback vertex set problem2-approximation algorithms
Related Items (35)
The size of graphs with given feedback vertex number ⋮ On the Complexity of Singly Connected Vertex Deletion ⋮ On the feedback vertex set polytope of a series-parallel graph ⋮ Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms ⋮ Using fractional primal-dual to schedule split intervals with demands ⋮ A primal-dual approach to approximation of node-deletion problems for matroidal properties ⋮ Inapproximability of $H$-Transversal/Packing ⋮ MIP formulations for induced graph optimization problems: a tutorial ⋮ A Linear Kernel for Planar Feedback Vertex Set ⋮ Improved approximation algorithms for hitting 3-vertex paths ⋮ Packing cycles exactly in polynomial time ⋮ A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem ⋮ Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem ⋮ A naive algorithm for feedback vertex set ⋮ The vertex cover \(P_3\) problem in cubic graphs ⋮ A primal-dual approximation algorithm for the vertex cover \(P^3\) problem ⋮ A fixed-parameter algorithm for the vertex cover \(P_3\) problem ⋮ Solving the feedback vertex set problem on undirected graphs ⋮ Efficient algorithm for the vertex cover \(P_k\) problem on cacti ⋮ On the minimum feedback vertex set problem: Exact and enumeration algorithms ⋮ Two feedback problems for graphs with bounded tree-width ⋮ Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms ⋮ A linear time algorithm for the minimum-weight feedback vertex set problem in series-parallel graphs ⋮ Disjoint cycles intersecting a set of vertices ⋮ Hitting Forbidden Minors: Approximation and Kernelization ⋮ An approximation algorithm for the \(l\)-pseudoforest deletion problem ⋮ Constant factor approximation for tracking paths and fault tolerant feedback vertex set ⋮ Constant factor approximation for tracking paths and fault tolerant feedback vertex set ⋮ Half-integrality, LP-branching, and FPT Algorithms ⋮ Euler Digraphs ⋮ On the complexity of singly connected vertex deletion ⋮ Unnamed Item ⋮ Fixed-parameter tractability for subset feedback set problems with parity constraints ⋮ Approximation algorithms for hitting subgraphs ⋮ Improved approximation for orienting mixed graphs
Cites Work
- A primal-dual approximation algorithm for generalized Steiner network problems
- Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
- Approximating Minimum Subset Feedback Sets in Undirected Graphs with Applications
- Primal-dual approximation algorithms for feedback problems in planar graphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
