On the spanning tree polyhedron
From MaRDI portal
Publication:1122482
DOI10.1016/0167-6377(89)90029-1zbMath0675.90060OpenAlexW2093080906MaRDI QIDQ1122482
Publication date: 1989
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0167-6377(89)90029-1
Programming involving graphs or networks (90C35) Trees (05C05) Integer programming (90C10) Combinatorial optimization (90C27) Polytopes and polyhedra (52Bxx)
Related Items
The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets ⋮ Network loading problem: valid inequalities from 5- and higher partitions ⋮ On two-connected subgraph polytopes ⋮ Chvátal-Gomory cuts for the Steiner tree problem ⋮ Fairest edge usage and minimum expected overlap for random spanning trees ⋮ Blocking duality for \(p\)-modulus on networks and applications ⋮ Spanning tree modulus for secure broadcast games ⋮ On a partition LP relaxation for min-cost 2-node connected spanning subgraphs ⋮ Fixed charge multicommodity network design using \(p\)-partition facets ⋮ Hepp's bound for Feynman graphs and matroids ⋮ A note on the generalized Steiner tree polytope ⋮ New Valid Inequalities for the Optimal Communication Spanning Tree Problem ⋮ Separating from the dominant of the spanning tree polytope ⋮ A partition-based relaxation for Steiner trees ⋮ Branch-and-cut approaches for chance-constrained formulations of reliable network design problems ⋮ Generalized network design problems. ⋮ The generalized minimum spanning tree problem: Polyhedral analysis and branch-and-cut algorithm ⋮ Branch-and-Cut Techniques for Solving Realistic Two-Layer Network Design Problems
Cites Work
- On the Problem of Decomposing a Graph into n Connected Factors
- Edge-Disjoint Spanning Trees of Finite Graphs
- Minimum partition of a matroid into independent subsets
- Lehmans switching game and a theorem of Tutte and Nash-Williams
- Blocking and anti-blocking pairs of polyhedra
- Matroids and the greedy algorithm
