Solving the feedback vertex set problem on undirected graphs
From MaRDI portal
Publication:1975362
DOI10.1016/S0166-218X(99)00180-8zbMath0946.90098WikidataQ126621766 ScholiaQ126621766MaRDI QIDQ1975362
Marco Trubian, Francesco Maffioli, Lorenzo Brunetta
Publication date: 9 April 2000
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)
Related Items (9)
On the feedback vertex set polytope of a series-parallel graph ⋮ Feedback vertex sets in mesh-based networks ⋮ New upper bounds on feedback vertex numbers in butterflies ⋮ Decycling bipartite graphs ⋮ New formulations and branch-and-cut procedures for the longest induced path problem ⋮ MIP formulations for induced graph optimization problems: a tutorial ⋮ Maximum weighted induced forests and trees: new formulations and a computational comparative review ⋮ On the minimum feedback vertex set problem: Exact and enumeration algorithms ⋮ Compact formulations and an iterated local search-based matheuristic for the minimum weighted feedback vertex set problem
Cites Work
- Unnamed Item
- Unnamed Item
- A linear-time algorithm for the weighted feedback vertex problem on interval graphs
- On locating minimum feedback vertex sets
- Almost exact minimum feedback vertex set in meshes and butterflies
- A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
- Solution of large weighted equicut problems
- Feedback vertex sets and cyclically reducible graphs
- A Greedy Heuristic for the Set-Covering Problem
- Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
- Tabu Search—Part I
- A polyhedral approach to the feedback vertex set problem
- Feedback vertex set on cocomparability graphs
- Reducibility among Combinatorial Problems
This page was built for publication: Solving the feedback vertex set problem on undirected graphs
