Approximations for the maximum acyclic subgraph problem

DOI10.1016/0020-0190(94)00086-7zbMath0942.68644OpenAlexW2072500816WikidataQ59650035 ScholiaQ59650035MaRDI QIDQ1332750

Shlomi Rubinstein, Refael Hassin

Publication date: 14 August 2000

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(94)00086-7

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Approximations of arbitrary relations by partial orders, A survey on the linear ordering problem for weighted or unweighted tournaments, Tight Localizations of Feedback Sets, The free boundary problem without initial condition, On the maximum acyclic subgraph problem under disjunctive constraints, Crossing-constrained hierarchical drawings, Maximal Acyclic Subgraphs and Closest Stable Matrices, An updated survey on the linear ordering problem for weighted or unweighted tournaments, Sequential Monte Carlo for maximum weight subgraphs with application to solving image jigsaw puzzles, Combinatorial algorithms for feedback problems in directed graphs, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A branch and bound algorithm for the acyclic subgraph problem
• How to make a digraph strongly connected
• Optimization, approximation, and complexity classes
• Geometric algorithms and combinatorial optimization
• Exact and heuristic algorithms for the weighted feedback arc set problem: A special case of the skew-symmetric quadratic assignment problem
• On the acyclic subgraph polytope
• Finding a minimum feedback arc set in reducible flow graphs
• An Analysis of the Greedy Heuristic for Independence Systems
• Approximative Algorithms for Discrete Optimization Problems
• Fair edge deletion problems
• Node-and edge-deletion NP-complete problems