The st-bond polytope on series-parallel graphs

DOI10.1051/RO/2018035MaRDI QIDQ4611490zbMATH OpenOpenAlexFDO

Authors Roland Grappe, Mathieu Lacroix

Publication date 18 January 2019

Published in RAIRO - Operations Research (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1051/ro/2018035

zbMATH Keywords

series-parallel graphbond\(st\)-bond polytopeminimal \(st\)-cut

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Recommendations

• Circuit and bond polytopes on series-parallel graphs
• On the stable set polytope of a series-parallel graph
• Arborescence polytopes for series-parallel graphs
• 2-clique-bond of stable set polyhedra
• The Steiner Traveling Salesman Polytope and Related Polyhedra

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• Circuit and bond polytopes on series-parallel graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• Lexicographical polytopes
• Maximal Flow Through a Network
• On the cut polytope
• On the dimension of projected polyhedra
• On the dominant of the \(s\)-\(t\)-cut polytope: vertices, facets, and adjacency
• Parallel recognition of series-parallel graphs
• The Concavity and Intersection Properties for Integral Polyhedra
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Topology of series-parallel networks
• When the cut condition is enough, a complete characterization for multiflow problems in series-parallel networks

Cited in

(4)

• On the bond polytope
• k-edge connected polyhedra on series-parallel graphs
• Circuit and bond polytopes on series-parallel graphs
• Arborescence polytopes for series-parallel graphs

This page was built for publication: The \(st\)-bond polytope on series-parallel graphs

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