The Steiner tree polytope and related polyhedra
From MaRDI portal
Publication:1322552
DOI10.1007/BF01582064zbMath0808.90124MaRDI QIDQ1322552
Publication date: 5 May 1994
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
projectionfacetsseries-parallel graphsformulationspolyhedral characterizationvertex weighted Steiner tree problem
Related Items
The Steiner cycle polytope, Arborescence polytopes for series-parallel graphs, Optimal capacitated ring trees, On the feedback vertex set polytope of a series-parallel graph, Lagrangian and branch-and-cut approaches for upgrading spanning tree problems, Chvátal-Gomory cuts for the Steiner tree problem, Influence Maximization with Latency Requirements on Social Networks, An extended formulation of the convex recoloring problem on a tree, General variable neighborhood search approach to group Steiner tree problem, A linear programming based approach to the Steiner tree problem with a fixed number of terminals, Solving Steiner trees: Recent advances, challenges, and perspectives, Weighted target set selection on trees and cycles, Vertex covering with capacitated trees, A note on the generalized Steiner tree polytope, Polyhedral study of the connected subgraph problem, Stronger MIP formulations for the Steiner forest problem, An Exact Algorithm for the Steiner Forest Problem, A computational study on the maximum-weight bounded-degree rooted tree problem, Binary Steiner trees: structural results and an exact solution approach, Traveling salesman path problems, A partition-based relaxation for Steiner trees, Cutting planes in integer and mixed integer programming, Decomposition and dynamic cut generation in integer linear programming, On survivable network polyhedra, MIP models for connected facility location: a theoretical and computational study, Steiner trees and polyhedra, Models and branch‐and‐cut algorithms for the Steiner tree problem with revenues, budget and hop constraints, The \(k\)-Cardinality Tree Problem: reformulations and Lagrangian relaxation, Using a hybrid of exact and genetic algorithms to design survivable networks, The node-edge weighted 2-edge connected subgraph problem: linear relaxation, facets and separation, Generalized network design problems., Using rank-1 lift-and-project closures to generate cuts for 0-1 MIPs, a computational investigation, Strong lower bounds for the prize collecting Steiner problem in graphs, Projections of the capacitated network loading problem, \(k\)-edge connected polyhedra on series-parallel graphs, Algorithms for a multi-level network optimization problem, An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem, Non delayed relax-and-cut algorithms
Cites Work
- 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
- Arborescence polytopes for series-parallel graphs
- Two-edge connected spanning subgraphs and polyhedra
- The Steiner tree problem. II: Properties and classes of facets
- Topology of series-parallel networks
- 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
- Generalized steiner problem in series-parallel networks
- Forbidden subgraphs and graph decomposition
- Some generalizations of the steiner problem in graphs
- The node-weighted steiner tree problem
- Linear-time computability of combinatorial problems on series-parallel graphs
- Graph Theory and Integer Programming
- A catalog of steiner tree formulations
- A Selection Problem of Shared Fixed Costs and Network Flows
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
