Separating from the dominant of the spanning tree polytope

DOI10.1016/0167-6377(92)90045-5MaRDI QIDQ1200792zbMATH OpenOpenAlexFDO

Authors 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

maximum flow problemsmost violated inequalitypartition inequalitiesseparation problemspanning tree polytope of a graph

Mathematics Subject Classification ID

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

Recommendations

• On the spanning tree polyhedron
• Separation algorithm for tree partitioning inequalities
• Separation of partition inequalities
• Publication:3484640
• The vertex separator problem: a polyhedral investigation

Cites work

• Blocking and anti-blocking pairs of polyhedra
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• New primal and dual matching heuristics
• On the spanning tree polyhedron
• Optimal attack and reinforcement of a network

Cited in

(26)

• A new algorithm for the intersection of a line with the independent set polytope of a matroid
• Minimizing symmetric submodular functions
• Random sampling and greedy sparsification for matroid optimization problems
• A faster algorithm for computing the strength of a network
• Vulnerability issues of star graphs, alternating group graphs and split-stars: Strength and toughness
• Characterizing the flow equivalent trees of a network
• Separation of partition inequalities for the \((1,2)\)-survivable network design problem
• On two-connected subgraph polytopes
• On the \(k\)-cut problem
• On some algorithmic aspects of hypergraphic matroids
• Separation of partition inequalities with terminals
• k-edge connected polyhedra on series-parallel graphs
• Network reinforcement
• Two-edge connected subgraphs with bounded rings: Polyhedral results and branch-and-cut
• Graphic submodular function minimization: a graphic approach and applications
• Separation algorithm for tree partitioning inequalities
• A linear programming approach to increasing the weight of all minimum spanning trees
• Computing weighted strength and applications to partitioning
• scientific article; zbMATH DE number 2230273 (Why is no real title available?)
• Optimal hierarchical clustering on a graph
• Design of survivable networks with low connectivity requirements
• Faster algorithms for security games on matroids
• Finding the maximum subgraph of prescribed strength
• A faster algorithm for computing the principal sequence of partitions of a graph
• Design of survivable IP-over-optical networks
• A fast exact algorithm for the problem of optimum cooperation and the structure of its solutions

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

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