On the maximum acyclic subgraph problem under disjunctive constraints

DOI10.1016/J.IPL.2014.07.013MaRDI QIDQ477599zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

computational complexityapproximation algorithmsdisjunctive constraintsmaximum acyclic subgraph problem

Mathematics Subject Classification ID

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)

Recommendations

• Paths, trees and matchings under disjunctive constraints
• The maximum flow problem with disjunctive constraints
• Tight Bounds for the Maximum Acyclic Subgraph Problem
• Fundamentals of Computation Theory
• On the acyclic subgraph polytope

Cites work

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

Cited in

(6)

• Subset sum problems with digraph constraints
• A unifying model for locally constrained spanning tree problems
• Tight Bounds for the Maximum Acyclic Subgraph Problem
• Paths, trees and matchings under disjunctive constraints
• Cable tree wiring -- benchmarking solvers on a real-world scheduling problem with a variety of precedence constraints
• scientific article; zbMATH DE number 1833409 (Why is no real title available?)

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)