The feedback arc set problem with triangle inequality is a vertex cover problem

DOI10.1007/s00453-013-9811-2zbMath1306.05079OpenAlexW2173656554MaRDI QIDQ486997

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

zbMATH Keywords

approximation algorithmsfeedback arc set probleminteger linear program formulation

Mathematics Subject Classification ID

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