The generalized dependency constrained spanning tree problem

DOI10.1016/j.entcs.2019.08.062OpenAlexW2979218355WikidataQ113317367 ScholiaQ113317367MaRDI QIDQ2132411

Luiz Alberto do Carmo Viana, Manoel B. Campêlo

Publication date: 27 April 2022

Full work available at URL: https://doi.org/10.1016/j.entcs.2019.08.062

zbMATH Keywords

NP-hardnessdependency constrained spanning tree probleminnaproximability

Mathematics Subject Classification ID

Mathematical programming (90Cxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Branch-and-cut-and-price algorithms for the degree constrained minimum spanning tree problem
• The minimum spanning tree problem with conflict constraints and its variations
• The min-degree constrained minimum spanning tree problem: formulations and branch-and-cut algorithm
• Paths, trees and matchings under disjunctive constraints
• Min-degree constrained minimum spanning tree problem: new formulation via Miller-Tucker-Zemlin constraints
• Min-degree constrained minimum spanning tree problem with fixed centrals and terminals: complexity, properties and formulations
• A branch and cut algorithm for minimum spanning trees under conflict constraints
• Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations
• Matroid Intersection
• Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal
• Matroids and the greedy algorithm
• Comparison of algorithms for the degree constrained minimum spanning tree

This page was built for publication: The generalized dependency constrained spanning tree problem