The feedback arc set problem with triangle inequality is a vertex cover problem
DOI10.1007/S00453-013-9811-2zbMATH Open1306.05079OpenAlexW2173656554MaRDI QIDQ486997FDOQ486997
Publication date: 19 January 2015
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-013-9811-2
Recommendations
- The feedback arc set problem with triangle inequality is a vertex cover problem
- An exact method for the minimum feedback arc set problem
- Combinatorial algorithms for feedback problems in directed graphs
- scientific article; zbMATH DE number 825126
- Tight upper bounds for minimum feedback arc sets of regular graphs
Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35) Approximation algorithms (68W25) Integer programming (90C10) Hypergraphs (05C65)
Cites Work
- Reducibility among Combinatorial Problems
- On the approximability of single-machine scheduling with precedence constraints
- Aggregating inconsistent information
- Title not available (Why is that?)
- Approximate Set Covering in Uniform Hypergraphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
- Aggregation of partial rankings, \(p\)-ratings and top-\(m\) lists
- Approximating minimum feedback sets and multicuts in directed graphs
- On the approximability of the maximum common subgraph problem
- Polynomial time approximation algorithms for machine scheduling: Ten open problems
- Title not available (Why is that?)
- Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant
- Divide-and-conquer approximation algorithms via spreading metrics
- On a theorem of Lovász on covers in \(r\)-partite hypergraphs
- Packing directed circuits fractionally
- Single machine precedence constrained scheduling is a Vertex cover problem
- Optimal Long Code Test with One Free Bit
- Vertex cover in graphs with locally few colors
- Deterministic Pivoting Algorithms for Constrained Ranking and Clustering Problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Improved Approximation Algorithms for Bipartite Correlation Clustering
- Single-Machine Scheduling with Precedence Constraints
- Title not available (Why is that?)
This page was built for publication: The feedback arc set problem with triangle inequality is a vertex cover problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q486997)
