Finding totally independent spanning trees with linear integer programming

DOI10.1007/978-3-319-09174-7_13MaRDI QIDQ3195324zbMATH OpenOpenAlexFDO

Authors

Publication date 16 October 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-09174-7_13

zbMATH Keywords

branch-and-cut algorithmscombinatorial optimizationpacking connected dominating setstotally independent spanning trees

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• scientific article; zbMATH DE number 1953097
• Completely independent spanning trees in torus networks
• Completely independent spanning trees in (partial) \(k\)-trees
• scientific article; zbMATH DE number 2080244
• Almost disjoint spanning trees: relaxing the conditions for completely independent spanning trees

Cites work

• A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees
• An exact algorithm for the maximum leaf spanning tree problem.
• Approximation algorithms for connected dominating sets
• Benders decomposition, branch-and-cut, and hybrid algorithms for the minimum connected dominating set problem
• Completely independent spanning trees in the underlying graph of a line digraph
• Completely independent spanning trees in torus networks
• Design of survivable networks
• Design of Survivable Networks: A survey
• Edge-Disjoint Spanning Trees of Finite Graphs
• Finding minimum congestion spanning trees
• scientific article; zbMATH DE number 1953097 (Why is no real title available?)
• scientific article; zbMATH DE number 795222 (Why is no real title available?)
• scientific article; zbMATH DE number 795223 (Why is no real title available?)
• Independent spanning trees of chordal rings
• Independent spanning trees with small depths in iterated line digraphs
• Integer Polyhedra Arising from Certain Network Design Problems with Connectivity Constraints
• Minimal spanning trees with a constraint on the number of leaves
• On constructing \(k\)-connected \(k\)-dominating set in wireless ad hoc and sensor networks
• Orientation-based models for \(\{0,1,2\}\)-survivable network design: theory and practice
• Reformulations and solution algorithms for the maximum leaf spanning tree problem
• Steiner problem in networks: A survey
• The maximum-leaf spanning tree problem: Formulations and facets
• The minimum connected dominating set problem: formulation, valid inequalities and a branch-and-cut algorithm
• The multi-tree approach to reliability in distributed networks
• Two counterexamples on completely independent spanning trees

Cited in

(2)

• Efficient computation of tolerances in the weighted independent set problem for trees
• On the k-maximally-disjoint weighted spanning trees problem: variants, complexity and algorithms

This page was built for publication: Finding totally independent spanning trees with linear integer programming

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