The feedback arc set problem with triangle inequality is a vertex cover problem
From MaRDI portal
Publication:486997
DOI10.1007/s00453-013-9811-2zbMath1306.05079OpenAlexW2173656554MaRDI QIDQ486997
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
Extremal problems in graph theory (05C35) Integer programming (90C10) Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Single machine precedence constrained scheduling is a Vertex cover problem
- Approximating minimum feedback sets and multicuts in directed graphs
- Polynomial time approximation algorithms for machine scheduling: Ten open problems
- Packing directed circuits fractionally
- On a theorem of Lovász on covers in \(r\)-partite hypergraphs
- Vertex cover in graphs with locally few colors
- Aggregation of partial rankings, \(p\)-ratings and top-\(m\) lists
- On the Approximability of Single-Machine Scheduling with Precedence Constraints
- Divide-and-conquer approximation algorithms via spreading metrics
- Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant
- Deterministic Pivoting Algorithms for Constrained Ranking and Clustering Problems
- Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
- Approximate Set Covering in Uniform Hypergraphs
- Improved Approximation Algorithms for Bipartite Correlation Clustering
- Reducibility among Combinatorial Problems
- On the approximability of the maximum common subgraph problem
- Optimal Long Code Test with One Free Bit
- Single-Machine Scheduling with Precedence Constraints
- Aggregating inconsistent information
This page was built for publication: The feedback arc set problem with triangle inequality is a vertex cover problem
