Packing Steiner trees: Further facets

DOI10.1006/EUJC.1996.0004MaRDI QIDQ1908272zbMATH OpenOpenAlexFDO

Authors Alexander Martin, Martin Grötschel, Robert Weismantel

Publication date 14 July 1996

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/d9d4143501a2349fa3c64a8daaec25660ee169e4

zbMATH Keywords

cutting plane algorithmpathSteiner treeSteiner tree packingSteiner tree packing polyhedron

Mathematics Subject Classification ID

Trees (05C05) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (including graph drawing) in computer science (68R10)

Review text

Let \(G= (V, E)\) be a graph with positive integer capacities \(c_e\) for all \(e\in E\). For a subset \(T\) of \(V\), an edge set \(S\) of \(E\) is called a Steiner tree of \(T\) if for each pair of nodes \(u, v\in T\), \(S\) contains a path between \(u\) and \(v\). Let \(T_1,T_2,\dots, T_n\) be node subsets of \(G\). The Steiner tree packing problem is to find Steiner trees \(S_k\) of \(T_k\) for \(k= 1,2,\dots, n\), such that each edge \(e\in E\) is contained in at most \(c_e S_i\). This paper investigates the Steiner tree packing polyhedron, establishes several new classes of valid inequalities and gives sufficient (and necessary) conditions for these inequalities to be facet-defining. These inequalities can be used to be incorporated into an existing cutting plane algorithm.

Recommendations

• Packing Steiner trees: Polyhedral investigations
• The Steiner tree polytope and related polyhedra
• Steiner trees and polyhedra
• Publication:3484640
• scientific article; zbMATH DE number 2079349

Cited in

(19)

• Packing trees in communication networks
• The Steiner tree problem. II: Properties and classes of facets
• Comparison of formulations and a heuristic for packing Steiner trees in a graph
• The Steiner tree packing problem in VLSI design
• Packing Steiner trees: Polyhedral investigations
• Packing Steiner trees: A cutting plane algorithm and computational results
• Steiner tree packing revisited
• Hardness and approximation results for packing Steiner trees
• Approximation algorithms and hardness results for packing element-disjoint Steiner trees in planar graphs
• Chvátal-Gomory cuts for the Steiner tree problem
• The cavity approach for Steiner trees packing problems
• scientific article; zbMATH DE number 108281 (Why is no real title available?)
• Packing element-disjoint steiner trees
• Facet-inducing inequalities with acyclic supports for the caterpillar-packing polytope
• scientific article; zbMATH DE number 2196275 (Why is no real title available?)
• Packings and Steiner systems in polar spaces
• Steiner trees and polyhedra
• A branch-and-price algorithm for the Steiner tree packing problem.
• Mathematical methods for physical layout of printed circuit boards: an overview

This page was built for publication: Packing Steiner trees: Further facets

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