Separating from the dominant of the spanning tree polytope

DOI10.1016/0167-6377(92)90045-5zbMath0759.90090OpenAlexW1969468986MaRDI QIDQ1200792

Francisco Barahona

Publication date: 16 January 1993

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(92)90045-5

zbMATH Keywords

partition inequalitiesseparation problemmost violated inequalitymaximum flow problemsspanning tree polytope of a graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (22)

A faster algorithm for computing the principal sequence of partitions of a graph ⋮ Separation of partition inequalities with terminals ⋮ Computing Weighted Strength and Applications to Partitioning ⋮ Design of survivable IP-over-optical networks ⋮ On two-connected subgraph polytopes ⋮ Optimal hierarchical clustering on a graph ⋮ Graphic Submodular Function Minimization: A Graphic Approach and Applications ⋮ A linear programming approach to increasing the weight of all minimum spanning trees ⋮ Faster algorithms for security games on matroids ⋮ On the \(k\)-cut problem ⋮ A fast exact algorithm for the problem of optimum cooperation and the structure of its solutions ⋮ A new algorithm for the intersection of a line with the independent set polytope of a matroid ⋮ Unnamed Item ⋮ Minimizing symmetric submodular functions ⋮ Random sampling and greedy sparsification for matroid optimization problems ⋮ \(k\)-edge connected polyhedra on series-parallel graphs ⋮ On some algorithmic aspects of hypergraphic matroids ⋮ Network reinforcement ⋮ Two-edge connected subgraphs with bounded rings: Polyhedral results and branch-and-cut ⋮ Vulnerability issues of star graphs, alternating group graphs and split-stars: Strength and toughness ⋮ A faster algorithm for computing the strength of a network ⋮ Separation of partition inequalities for the \((1,2)\)-survivable network design problem

Cites Work

• Unnamed Item
• On the spanning tree polyhedron
• New primal and dual matching heuristics
• Optimal attack and reinforcement of a network
• Blocking and anti-blocking pairs of polyhedra

This page was built for publication: Separating from the dominant of the spanning tree polytope