An Exact Method for the Minimum Feedback Arc Set Problem
From MaRDI portal
Publication:5102057
DOI10.1145/3446429zbMath1499.68247OpenAlexW3158263509MaRDI QIDQ5102057
Ali Baharev, Arnold Neumaier, Tobias Achterberg, Hermann Schichl
Publication date: 6 September 2022
Published in: ACM Journal of Experimental Algorithmics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/3446429
linear ordering problemtearingminimum feedback vertex setminimum feedback arc setmaximum acyclic subgraph
Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- The linear ordering problem. Exact and heuristic methods in combinatorial optimization.
- A fast and effective heuristic for the feedback arc set problem
- Exact localisations of feedback sets
- SCIP: solving constraint integer programs
- Combinatorial algorithms for feedback problems in directed graphs
- A branch and bound algorithm for the acyclic subgraph problem
- Optimization, approximation, and complexity classes
- On the ratio of optimal integral and fractional covers
- Graph layout for applications in compiler construction
- On enumerating all minimal solutions of feedback problems
- Approximating minimum feedback sets and multicuts in directed graphs
- Packing directed circuits fractionally
- Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG
- Efficient exact algorithms through enumerating maximal independent sets and other techniques
- The linear ordering problem with cumulative costs
- A Suggested Computation for Maximal Multi-Commodity Network Flows
- On the NP-Hardness of Approximating Ordering Constraint Satisfaction Problems
- Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant
- New and Improved Bounds for the Minimum Set Cover Problem
- A Cutting Plane Algorithm for the Linear Ordering Problem
- Input-Output Analysis
- The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
- A fixed-parameter algorithm for the directed feedback vertex set problem
- On the power of unique 2-prover 1-round games
- A Design for Directed Graphs with Minimum Diameter
- On the acyclic subgraph polytope
- Finding a minimum feedback arc set in reducible flow graphs
- Generalized de Bruijn digraphs
- The Complexity of Enumeration and Reliability Problems
- A Greedy Heuristic for the Set-Covering Problem
- Design to Minimize Diameter on Building-Block Network
- Optimal Weighted Ancestry Relationships
- A Minimax Theorem for Directed Graphs
- Reducibility among Combinatorial Problems
- Finding All the Elementary Circuits of a Directed Graph
- Breaking cycles for minimizing crossings
- Computational Complexity
- Solution of a Large-Scale Traveling-Salesman Problem
- Ranking Tournaments
- Random Graphs
- Depth-First Search and Linear Graph Algorithms
