Solving the feedback vertex set problem on undirected graphs

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)

zbMATH Keywords

tabu searchbranch-and-cutlocal search heuristicfeedback vertex set

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Related Items (10)

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 ⋮ Integer programming formulations for the \(k\)-in-a-tree problem in graphs ⋮ 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
• Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs

This page was built for publication: Solving the feedback vertex set problem on undirected graphs