Tight Bounds for the Maximum Acyclic Subgraph Problem

DOI10.1006/JAGM.1997.0864MaRDI QIDQ4366872zbMATH OpenOpenAlexWikidataFDO

Authors Bonnie Berger, Peter W. Shor

Publication date 25 November 1997

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jagm.1997.0864

zbMATH Keywords

maximum acyclic subgraph problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On the maximum acyclic subgraph problem under disjunctive constraints
• The approximation of maximum subgraph problems
• scientific article; zbMATH DE number 1833409
• On the complexity of the maximum subgraph problem
• The Complexity of Acyclic Subhypergraph Problems
• Approximating Maximum Subgraphs without Short Cycles
• Approximating maximum subgraphs without short cycles
• The parallel complexity of approximation algorithms for the maximum acyclic subgraph problem
• Exact Algorithms for Maximum Acyclic Subgraph on a Superclass of Cubic Graphs

Cited in

(22)

• Bounded degree acyclic decompositions of digraphs.
• Improved algorithms via approximations of probability distributions
• Listing acyclic subgraphs and subgraphs of bounded girth in directed graphs
• Balanced vertex-orderings of graphs
• The covering threshold of a directed acyclic graph by directed acyclic subgraphs
• A survey on the linear ordering problem for weighted or unweighted tournaments
• Coloring graphs using two colors while avoiding monochromatic cycles
• Directed acyclic subgraph problem parameterized above the Poljak-Turzík bound
• The Complexity of Acyclic Subhypergraph Problems
• On Generating All Maximal Acyclic Subhypergraphs with Polynomial Delay
• The parallel complexity of approximation algorithms for the maximum acyclic subgraph problem
• When recursion is better than iteration: a linear-time algorithm for acyclicity with few error vertices
• Intersections of random hypergraphs and tournaments
• On the maximum acyclic subgraph problem under disjunctive constraints
• scientific article; zbMATH DE number 1833409 (Why is no real title available?)
• Maximal acyclic subgraphs and closest stable matrices
• Exact Algorithms for Maximum Acyclic Subgraph on a Superclass of Cubic Graphs
• Fundamentals of Computation Theory
• Extremal results on feedback arc sets in digraphs
• Upper bounds on the minimum size of feedback arc set of directed multigraphs with bounded degree
• Abstraction-based failure diagnosis for discrete event systems
• An updated survey on the linear ordering problem for weighted or unweighted tournaments

This page was built for publication: Tight Bounds for the Maximum Acyclic Subgraph Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4366872)