The feedback arc set problem with triangle inequality is a vertex cover problem
DOI10.1007/S00453-013-9811-2zbMATH Open1306.05079OpenAlexW2173656554MaRDI QIDQ486997FDOQ486997
Authors: Monaldo Mastrolilli 
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: ranking and clustering
- 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
- Deterministic pivoting algorithms for constrained ranking and clustering problems
- 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?)
Cited In (1)
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)
