Arborescence polytopes for series-parallel graphs

DOI10.1016/0166-218X(92)00035-KMaRDI QIDQ1329787zbMATH OpenWikidataFDO

Authors Michel X. Goemans

Publication date 1 December 1994

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

Full work available at URL https://doi.org/10.1016/0166-218X(92)00035-K

zbMATH Keywords

arborescencediscrete graphlinear inequalitiespolytopesseries-parallel graphs

Mathematics Subject Classification ID

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

Review text

A graph is called series-parallel if it does not contain any subgraph homeomorphic to the complete graph on 4 vertices. For a directed graph whose underlying graph is series-parallel, an \(r\)-arborescence is defined as a tree directed away from the root vertex \(r\). Given a set of terminals, a Steiner arborescence is an \(r\)-arborescence spanning this set. Associated with these arborescences the author defines the convex hulls of incidence vectors and characterizes these polytopes completely by linear inequalities.

Recommendations

• The Steiner tree polytope and related polyhedra
• The \(st\)-bond polytope on series-parallel graphs
• Facets of two Steiner arborescence polyhedra
• Circuit and bond polytopes on series-parallel graphs
• On the stable set polytope of a series-parallel graph

Cites work

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

Cited in

(14)

• Designing reliable tree networks with two cable technologies
• The Steiner tree polytope and related polyhedra
• Circuit and bond polytopes on series-parallel graphs
• Heuristic and exact algorithms for minimum-weight non-spanning arborescences
• Stronger MIP formulations for the Steiner forest problem
• k-edge connected polyhedra on series-parallel graphs
• Lehman's theorem and the directed Steiner tree problem
• The \(st\)-bond polytope on series-parallel graphs
• Opposite elements in clutters
• Steiner trees and polyhedra
• Enumerative problems for arborescences and monotone paths on polytope graphs
• Optimal connected subgraphs: Integer programming formulations and polyhedra
• Solving Steiner trees: Recent advances, challenges, and perspectives
• Vertex covering with capacitated trees

This page was built for publication: Arborescence polytopes for series-parallel graphs

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