Steiner trees and polyhedra

DOI10.1016/S0166-218X(00)00311-5zbMath0994.90136WikidataQ127344147 ScholiaQ127344147MaRDI QIDQ5946818

Hervé L. M. Kerivin, Ali Ridha Mahjoub, M. Didi Biha

Publication date: 30 July 2002

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

zbMATH Keywords

networkgraphpolytopeSteiner treefacetseries-parallel graphSteiner connected subgraph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05) Special polytopes (linear programming, centrally symmetric, etc.) (52B12)

Related Items

Routing of uncertain traffic demands, Chvátal-Gomory cuts for the Steiner tree problem, Solving Steiner trees: Recent advances, challenges, and perspectives, Polyhedral study of the connected subgraph problem, A partition-based relaxation for Steiner trees, On survivable network polyhedra, Design and dimensioning of hydrogen transmission pipeline networks

Cites Work

• Survivable networks, linear programming relaxations and the parsimonious property
• Path-distance heuristic for the Steiner problem in undirected networks
• Steiner's problem in graphs: Heuristic methods
• The Steiner tree problem
• Design of survivable networks
• The Steiner tree polytope and related polyhedra
• Tree polytope on 2-trees
• Arborescence polytopes for series-parallel graphs
• The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets
• The Steiner tree problem. II: Properties and classes of facets
• On the monotonization of polyhedra
• New approximation algorithms for the Steiner tree problems
• A faster approximation algorithm for the Steiner tree problem in graphs
• 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
• The node-weighted steiner tree problem
• Steiner problem in networks: A survey
• Reduction tests for the steiner problem in grapsh
• Computational Results with a Cutting Plane Algorithm for Designing Communication Networks with Low-Connectivity Constraints
• Polyhedra of the Equivalent Subgraph Problem and Some Edge Connectivity Problems
• The Complexity of Multiterminal Cuts
• A catalog of steiner tree formulations
• A comparison of Steiner tree relaxations
• Improved algorithms for the Steiner problem in networks
• Unnamed Item
• Unnamed Item
• Unnamed Item