On the maximum acyclic subgraph problem under disjunctive constraints

DOI10.1016/j.ipl.2014.07.013zbMath1304.05101OpenAlexW2021720298MaRDI QIDQ477599

Sílvia Maria Santana Mapa, Sebastián Urrutia

Publication date: 9 December 2014

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

Full work available at URL: https://doi.org/10.1016/j.ipl.2014.07.013

zbMATH Keywords

computational complexityapproximation algorithmsdisjunctive constraintsmaximum acyclic subgraph problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

A unifying model for locally constrained spanning tree problems ⋮ Cable tree wiring -- benchmarking solvers on a real-world scheduling problem with a variety of precedence constraints

Cites Work

• The maximum flow problem with disjunctive constraints
• Paths, trees and matchings under disjunctive constraints
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Geometric algorithms and combinatorial optimization.
• Approximations for the maximum acyclic subgraph problem
• On the NP-Hardness of Approximating Ordering Constraint Satisfaction Problems
• The Knapsack Problem with Conflict Graphs
• On the power of unique 2-prover 1-round games
• Reducibility among Combinatorial Problems