The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets
From MaRDI portal
Publication:1330902
DOI10.1007/BF01582573zbMath0821.90124OpenAlexW1974745840MaRDI QIDQ1330902
Publication date: 10 August 1994
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01582573
Programming involving graphs or networks (90C35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Integer programming (90C10)
Related Items
Exact approaches to the single-source network loading problem, Optimal capacitated ring trees, Branch-and-price algorithm for the resilient multi-level hop-constrained network design, Optimal relay node placement in delay constrained wireless sensor network design, The robust network loading problem with dynamic routing, Lehman's Theorem and the Directed Steiner Tree Problem, Optimal Steiner trees under node and edge privacy conflicts, Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem, Chvátal-Gomory cuts for the Steiner tree problem, Benders Decomposition, Branch-and-Cut, and Hybrid Algorithms for the Minimum Connected Dominating Set Problem, Solving Steiner trees: Recent advances, challenges, and perspectives, Optimizing the Design of a Wind Farm Collection Network, Vertex covering with capacitated trees, The Steiner connectivity problem, Coordinated cutting plane generation via multi-objective separation, New geometry-inspired relaxations and algorithms for the metric Steiner tree problem, A note on the generalized Steiner tree polytope, Polyhedral study of the connected subgraph problem, Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs, A tabu search heuristic for the generalized minimum spanning tree problem, Stronger MIP formulations for the Steiner forest problem, Facets of two Steiner arborescence polyhedra, An Exact Algorithm for the Steiner Forest Problem, Intermediate integer programming representations using value disjunctions, Binary Steiner trees: structural results and an exact solution approach, A partition-based relaxation for Steiner trees, On survivable network polyhedra, MIP models for connected facility location: a theoretical and computational study, Discrete relaxations of combinatorial programs, Steiner trees and polyhedra, A comparison of Steiner tree relaxations, Some formulations for the group Steiner tree problem, Models and branch‐and‐cut algorithms for the Steiner tree problem with revenues, budget and hop constraints, Approximation of Steiner forest via the bidirected cut relaxation, Towards optimizing the deployment of optical access networks, Idealness and 2-resistant sets, Generalized network design problems., Opposite Elements in Clutters, Using rank-1 lift-and-project closures to generate cuts for 0-1 MIPs, a computational investigation, Approaches to the Steiner Problem in Networks, Flots entiers et multiflots fractionnaires couplés par une contrainte de capacité, Distance Transformation for Network Design Problems, Unnamed Item, Graphs and Algorithms in Communication Networks on Seven League Boots, Towards a lifecycle oriented design of infrastructure by mathematical optimization, An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem, Directed Steiner problems with connectivity constraints, Separation of partition inequalities for the \((1,2)\)-survivable network design problem, Dimensioning multicast-enabled communications networks, Non delayed relax-and-cut algorithms
Cites Work
- Unnamed Item
- Unnamed Item
- On the spanning tree polyhedron
- The perfectly matchable subgraph polytope of a bipartite graph
- Steiner trees, partial 2–trees, and minimum IFI networks
- A dual ascent approach for steiner tree problems on a directed graph
- The traveling salesman problem on a graph and some related integer polyhedra
- Steiner trees, connected domination and strongly chordal graphs
- Steiner problem in networks: A survey
- An integer linear programming approach to the steiner problem in graphs
- Solving the Steiner Tree Problem on a Graph Using Branch and Cut
- On Steiner Minimal Trees with Rectilinear Distance
- Rectilinear steiner trees: Efficient special-case algorithms
- Steiner's problem in graphs and its implications
- The steiner problem in graphs
- Blocking and anti-blocking pairs of polyhedra
