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

zbMATH Keywords

approximation algorithmsfeedback arc set probleminteger linear program formulation

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 5605136 (Why is no real title available?)
• scientific article; zbMATH DE number 5485441 (Why is no real title available?)
• scientific article; zbMATH DE number 3902393 (Why is no real title available?)
• scientific article; zbMATH DE number 53952 (Why is no real title available?)
• scientific article; zbMATH DE number 1384868 (Why is no real title available?)
• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• scientific article; zbMATH DE number 3304772 (Why is no real title available?)
• Aggregating inconsistent information: ranking and clustering
• Aggregation of partial rankings, \(p\)-ratings and top-\(m\) lists
• Approximate Set Covering in Uniform Hypergraphs
• Approximating minimum feedback sets and multicuts in directed graphs
• Beating the random ordering is hard: every ordering CSP is approximation resistant
• Deterministic pivoting algorithms for constrained ranking and clustering problems
• Deterministic pivoting algorithms for constrained ranking and clustering problems
• Divide-and-conquer approximation algorithms via spreading metrics
• Improved approximation algorithms for bipartite correlation clustering
• On a theorem of Lovász on covers in \(r\)-partite hypergraphs
• On the approximability of single-machine scheduling with precedence constraints
• On the approximability of the maximum common subgraph problem
• Optimal Long Code Test with One Free Bit
• Packing directed circuits fractionally
• Polynomial time approximation algorithms for machine scheduling: Ten open problems
• Reducibility among combinatorial problems
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• Single machine precedence constrained scheduling is a Vertex cover problem
• Single-Machine Scheduling with Precedence Constraints
• Vertex cover in graphs with locally few colors

Cited in

(1)

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

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)