On the maximum acyclic subgraph problem under disjunctive constraints
DOI10.1016/J.IPL.2014.07.013zbMATH Open1304.05101OpenAlexW2021720298MaRDI QIDQ477599FDOQ477599
Authors: 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
Recommendations
computational complexityapproximation algorithmsdisjunctive constraintsmaximum acyclic subgraph problem
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Cites Work
- Reducibility among combinatorial problems
- Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
- Geometric algorithms and combinatorial optimization.
- On the power of unique 2-prover 1-round games
- The maximum flow problem with disjunctive constraints
- The Knapsack Problem with Conflict Graphs
- Paths, trees and matchings under disjunctive constraints
- Approximations for the maximum acyclic subgraph problem
- On the NP-Hardness of Approximating Ordering Constraint Satisfaction Problems
Cited In (6)
- Subset sum problems with digraph constraints
- Tight Bounds for the Maximum Acyclic Subgraph Problem
- Title not available (Why is that?)
- 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
- Paths, trees and matchings under disjunctive constraints
This page was built for publication: On the maximum acyclic subgraph problem under disjunctive constraints
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q477599)
