Arborescence polytopes for series-parallel graphs

DOI10.1016/0166-218X(92)00035-KzbMath0802.05040WikidataQ126866920 ScholiaQ126866920MaRDI QIDQ1329787

Michel X. Goemans

Publication date: 1 December 1994

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

polytopeslinear inequalitiesseries-parallel graphsarborescencediscrete graph

Mathematics Subject Classification ID

Trees (05C05) Graph theory (05C99) Directed graphs (digraphs), tournaments (05C20)

Related Items

Lehman's Theorem and the Directed Steiner Tree Problem, Optimal connected subgraphs: Integer programming formulations and polyhedra, Heuristic and exact algorithms for minimum-weight non-spanning arborescences, Solving Steiner trees: Recent advances, challenges, and perspectives, Vertex covering with capacitated trees, Stronger MIP formulations for the Steiner forest problem, Steiner trees and polyhedra, Opposite Elements in Clutters, Designing reliable tree networks with two cable technologies, The Steiner tree polytope and related polyhedra

Cites Work

• Unnamed Item
• On the stable set polytope of a series-parallel graph
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Polytope des independants d'un graphe série-parallèle
• The Steiner tree polytope and related polyhedra
• Two-edge connected spanning subgraphs and polyhedra
• Topology of series-parallel networks
• Steiner trees, partial 2–trees, and minimum IFI networks
• The traveling salesman problem on a graph and some related integer polyhedra
• Generalized steiner problem in series-parallel networks
• Forbidden subgraphs and graph decomposition
• The node-weighted steiner tree problem
• Linear-time computability of combinatorial problems on series-parallel graphs
• The Equivalent Subgraph and Directed Cut Polyhedra on Series-Parallel Graphs
• The Graph Partitioning Polytope on Series-Parallel and 4-Wheel Free Graphs
• A catalog of steiner tree formulations