An integer linear programming approach to the steiner problem in graphs

DOI10.1002/NET.3230100207MaRDI QIDQ3890443zbMATH OpenOpenAlexFDO

Authors Y. P. Aneja

Publication date 1980

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.3230100207

zbMATH Keywords

connected undirected graphinteger linear programmingminimal weighted treerow generation schemeset covering formulationSteiner problem in graphs

Mathematics Subject Classification ID

Trees (05C05) Numerical mathematical programming methods (65K05) Integer programming (90C10) Programming involving graphs or networks (90C35)

Cited in

(43)

• Steiner problem in Halin networks
• The telephonic switching centre network problem: Formalization and computational experience
• A constrained Steiner tree problem
• Minmax combinatorial optimization
• Finding minimum cost directed trees with demands and capacities
• Path-distance heuristic for the Steiner problem in undirected networks
• Steiner's problem in graphs: Heuristic methods
• Algorithms for a multi-level network optimization problem
• Tree polytope on 2-trees
• The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets
• Delay-related secondary objectives for rectilinear Steiner minimum trees.
• Two variations of the minimum Steiner problem
• On Steiner trees and minimum spanning trees in hypergraphs
• On the core of the minimum cost Steiner tree game in networks
• A branch-and-cut algorithm for the Steiner tree problem with delays
• Mixed integer programming formulations for Steiner tree and quality of service multicast tree problems
• 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
• Chvátal-Gomory cuts for the Steiner tree problem
• An exact algorithm for the Steiner tree problem with delays
• A dual ascent approach for steiner tree problems on a directed graph
• Branch and Cut based on the volume algorithm: Steiner trees in graphs and Max-cut
• Approaches to the Steiner Problem in Networks
• An integer programming formulation of the Steiner problem in graphs
• Strong Steiner tree approximations in practice
• Parallel algorithms for a multi-level network optimization problem
• Distance transformation for network design problems
• A partition-based relaxation for Steiner trees
• Two Constant Approximation Algorithms for Node-Weighted Steiner Tree in Unit Disk Graphs
• A faster approximation algorithm for the Steiner problem in graphs
• A comparison of Steiner tree relaxations
• Improved algorithms for the Steiner problem in networks
• Approximation algorithms for Steiner forest: An experimental study
• Solving Steiner trees: Recent advances, challenges, and perspectives
• Vertex covering with capacitated trees
• Steiner problems on directed acyclic graphs
• Tree network design avoiding congestion
• Survivable networks, linear programming relaxations and the parsimonious property
• A multicast problem with shared risk cost
• Branch-and-cut approaches for chance-constrained formulations of reliable network design problems
• Node-weighted Steiner tree approximation in unit disk graphs
• 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

This page was built for publication: An integer linear programming approach to the steiner problem in graphs

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