A polyhedral approach to the feedback vertex set problem

DOI10.1007/3-540-61310-2_33zbMath1415.90063MaRDI QIDQ4645941

Meinrad Funke, Gerhard Reinelt

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_33

zbMATH Keywords

primal heuristic; integer programming formulation; incidence vector; cycle inequality; feedback problem

Mathematics Subject Classification ID

90C10: Integer programming

90C27: Combinatorial optimization

Related Items

Unnamed Item, Algorithms for finding maximum transitive subtournaments, Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem, Introduction to ABACUS -- a branch-and-cut system, Solving the feedback vertex set problem on undirected graphs, Compact formulations and an iterated local search-based matheuristic for the minimum weighted feedback vertex set problem, Almost always observable hybrid systems, Fixed-parameter tractability for subset feedback set problems with parity constraints, A constraint programming approach to cutset problems, Maximum Weighted Induced Bipartite Subgraphs and Acyclic Subgraphs of Planar Cubic Graphs

Uses Software

• CPLEX

Cites Work

• On the feedback vertex set problem for a planar graph
• Weakly bipartite graphs and the max-cut problem
• Introduction to ABACUS -- a branch-and-cut system
• On the acyclic subgraph polytope
• General topological results on the construction of a minimum essential set of a directed graph
• Robust linear algorithms for cutsets
• Reducibility among Combinatorial Problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item