An integer linear programming approach to the steiner problem in graphs
From MaRDI portal
Publication:3890443
DOI10.1002/net.3230100207zbMath0445.90087OpenAlexW2007503572MaRDI QIDQ3890443
Publication date: 1980
Published in: Networks (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/net.3230100207
integer linear programmingconnected undirected graphSteiner problem in graphsminimal weighted treerow generation schemeset covering formulation
Programming involving graphs or networks (90C35) Trees (05C05) Numerical mathematical programming methods (65K05) Integer programming (90C10)
Related Items (43)
An Exact Algorithm for the Steiner Tree Problem with Delays ⋮ The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets ⋮ Steiner problem in Halin networks ⋮ The telephonic switching centre network problem: Formalization and computational experience ⋮ On the core of the minimum cost Steiner tree game in networks ⋮ Node-weighted Steiner tree approximation in unit disk graphs ⋮ Parallel algorithms for a multi-level network optimization problem ⋮ Chvátal-Gomory cuts for the Steiner tree problem ⋮ A constrained Steiner tree problem ⋮ Minmax combinatorial optimization ⋮ A branch-and-cut algorithm for the Steiner tree problem with delays ⋮ Approximation algorithms for Steiner forest: An experimental study ⋮ An integer programming formulation of the Steiner problem in graphs ⋮ Solving Steiner trees: Recent advances, challenges, and perspectives ⋮ Vertex covering with capacitated trees ⋮ Steiner problems on directed acyclic graphs ⋮ Tree network design avoiding congestion ⋮ Delay-related secondary objectives for rectilinear Steiner minimum trees. ⋮ Strong Steiner Tree Approximations in Practice ⋮ Mixed integer programming formulations for Steiner tree and quality of service multicast tree problems ⋮ Finding minimum cost directed trees with demands and capacities ⋮ Path-distance heuristic for the Steiner problem in undirected networks ⋮ A dual ascent approach for steiner tree problems on a directed graph ⋮ Survivable networks, linear programming relaxations and the parsimonious property ⋮ Steiner's problem in graphs: Heuristic methods ⋮ A faster approximation algorithm for the Steiner problem in graphs ⋮ A multicast problem with shared risk cost ⋮ A partition-based relaxation for Steiner trees ⋮ Two variations of the minimum Steiner problem ⋮ A comparison of Steiner tree relaxations ⋮ Improved algorithms for the Steiner problem in networks ⋮ An efficient algorithm for the Steiner tree problem with revenue, bottleneck and hop objective functions ⋮ Reformulations and solution algorithms for the maximum leaf spanning tree problem ⋮ Branch-and-cut approaches for chance-constrained formulations of reliable network design problems ⋮ Approaches to the Steiner Problem in Networks ⋮ Distance Transformation for Network Design Problems ⋮ Two Constant Approximation Algorithms for Node-Weighted Steiner Tree in Unit Disk Graphs ⋮ Branch and Cut based on the volume algorithm: Steiner trees in graphs and Max-cut ⋮ Algorithms for a multi-level network optimization problem ⋮ Speeding up dynamic programming with representative sets: an experimental evaluation of algorithms for Steiner Tree on tree decompositions ⋮ An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem ⋮ Tree polytope on 2-trees ⋮ On Steiner trees and minimum spanning trees in hypergraphs
This page was built for publication: An integer linear programming approach to the steiner problem in graphs
