A dual ascent approach for steiner tree problems on a directed graph

DOI10.1007/BF02612335zbMath0532.90092OpenAlexW2020586530MaRDI QIDQ3315294

Publication date: 1984

Published in: Mathematical Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02612335

zbMATH Keywords

Steiner tree problem directed graph computational results heuristic procedure directed spanning tree dual ascent procedure uncapacitated plant location directed subtree lower bounds to the optimal solution value

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Numerical mathematical programming methods (65K05) Integer programming (90C10) Inventory, storage, reservoirs (90B05)

Related Items (only showing first 100 items - show all)

Increasing digraph arc-connectivity by arc addition, reversal and complement ⋮ A heuristic approach for combined equipment-planning and routing in multi-layer SDH/WDM networks ⋮ The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets ⋮ Topological design of a two-level network with ring-star configuration ⋮ Comparison of formulations and a heuristic for packing Steiner trees in a graph ⋮ Layered graph approaches for combinatorial optimization problems ⋮ The telephonic switching centre network problem: Formalization and computational experience ⋮ A monotonic, dual-based bounding procedure for integer programs ⋮ On the core of the minimum cost Steiner tree game in networks ⋮ Models and algorithms for network reduction ⋮ A robust and scalable algorithm for the Steiner problem in graphs ⋮ Improved bounds for large scale capacitated arc routing problem ⋮ Optimal Steiner trees under node and edge privacy conflicts ⋮ On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree ⋮ A practical greedy approximation for the directed Steiner tree problem ⋮ New primal-dual algorithms for Steiner tree problems ⋮ Unnamed Item ⋮ Routing and capacity assignment in backbone communication networks ⋮ Chvátal-Gomory cuts for the Steiner tree problem ⋮ On the Exact Solution of Prize-Collecting Steiner Tree Problems ⋮ An exact algorithm to extend lifetime through roles allocation in sensor networks with connectivity constraints ⋮ A Practical Greedy Approximation for the Directed Steiner Tree Problem ⋮ A factoring approach for the Steiner tree problem in undirected networks ⋮ A constrained Steiner tree problem ⋮ Minmax combinatorial optimization ⋮ The Performance of greedy algorithms for the on-line steiner tree and related problems ⋮ Matheuristics: survey and synthesis ⋮ Optimal connected subgraphs: Integer programming formulations and polyhedra ⋮ Multicast routing under quality of service constraints for vehicular ad hoc networks: mathematical formulation and a relax‐and‐fix heuristic ⋮ Stronger path‐based extended formulation for the Steiner tree problem ⋮ A linear programming based approach to the Steiner tree problem with a fixed number of terminals ⋮ An integer programming formulation of the Steiner problem in graphs ⋮ Heuristic and exact algorithms for minimum-weight non-spanning arborescences ⋮ Steiner tree packing revisited ⋮ Strategic cooperation in cost sharing games ⋮ Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm ⋮ Thinning out Steiner trees: a node-based model for uniform edge costs ⋮ SCIP-Jack -- a solver for STP and variants with parallelization extensions ⋮ LP extreme points and cuts for the fixed-charge network design problem ⋮ Lagrangean decomposition: A model yielding stronger lagrangean bounds ⋮ A dual ascent algorithm for the 1-tree relaxation of the symmetric traveling salesman problem ⋮ The ring-star problem: a new integer programming formulation and a branch-and-cut algorithm ⋮ Tree network design avoiding congestion ⋮ New geometry-inspired relaxations and algorithms for the metric Steiner tree problem ⋮ Combining NP-Hard Reduction Techniques and Strong Heuristics in an Exact Algorithm for the Maximum-Weight Connected Subgraph Problem ⋮ A Dual Ascent-Based Branch-and-Bound Framework for the Prize-Collecting Steiner Tree and Related Problems ⋮ Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs ⋮ Two-Dimensional Phase Unwrapping via Balanced Spanning Forests ⋮ Strong Steiner Tree Approximations in Practice ⋮ Mixed integer programming formulations for Steiner tree and quality of service multicast tree problems ⋮ Using separation algorithms to generate mixed integer model reformulations ⋮ Finding minimum cost directed trees with demands and capacities ⋮ An approach for the Steiner problem in directed graphs ⋮ Compact systems for T-join and perfect matching polyhedra of graphs with bounded genus ⋮ Path-distance heuristic for the Steiner problem in undirected networks ⋮ Decomposition methods for the two-stage stochastic Steiner tree problem ⋮ Solving minimum-cost shared arborescence problems ⋮ An algorithmic framework for the exact solution of tree-star problems ⋮ Viral systems: A new bio-inspired optimisation approach ⋮ LINEAR AND INTEGER PROGRAMMING TECHNIQUES FOR COOPERATIVE GAMES ⋮ THE EFFECT OF ASYMMETRY ON THE ON-LINE MULTICAST ROUTING PROBLEM ⋮ On cuts and matchings in planar graphs ⋮ Survivable networks, linear programming relaxations and the parsimonious property ⋮ Steiner's problem in graphs: Heuristic methods ⋮ A multicast problem with shared risk cost ⋮ A partition-based relaxation for Steiner trees ⋮ Algorithmic expedients for the \(S\)-labeling problem ⋮ Dual-based approach for a hub network design problem under non-restrictive policy ⋮ Worst-case performance of Wong's Steiner tree heuristic ⋮ Two variations of the minimum Steiner problem ⋮ A distributed dual ascent algorithm for the Hop-constrained Steiner tree problem ⋮ A comparison of Steiner tree relaxations ⋮ Improved algorithms for the Steiner problem in networks ⋮ A distributed dual ascent algorithm for Steiner problems in multicast routing ⋮ Mathematical methods for physical layout of printed circuit boards: an overview ⋮ Reformulations and solution algorithms for the maximum leaf spanning tree problem ⋮ Heuristic algorithms for packing of multiple-group multicasting ⋮ Capacitated ring arborescence problems with profits ⋮ An exact solution framework for the minimum cost dominating tree problem ⋮ Implications, conflicts, and reductions for Steiner trees ⋮ Approaches to the Steiner Problem in Networks ⋮ On the core of network synthesis games ⋮ Combinatorial optimization in system configuration design ⋮ Distance Transformation for Network Design Problems ⋮ An application-oriented guide for designing Lagrangean dual ascent algorithms ⋮ Unnamed Item ⋮ Minimum directed 1-subtree relaxation for score orienteering problem ⋮ Generalized spanning trees ⋮ Mixed-integer programming approaches for the tree \(t^*\)-spanner problem ⋮ Algorithms for a multi-level network optimization problem ⋮ An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem ⋮ Worst-case performance of some heuristics for Steiner's problem in directed graphs ⋮ Directed Steiner problems with connectivity constraints ⋮ The Steiner tree polytope and related polyhedra ⋮ Tree polytope on 2-trees ⋮ Uncapacitated point-to-multipoint network flow problem and its application to multicasting in telecommunication networks ⋮ On Steiner trees and minimum spanning trees in hypergraphs ⋮ Dimensioning multicast-enabled communications networks ⋮ Upper and lower bounding strategies for the generalized minimum spanning tree problem ⋮ Solving Steiner trees: Recent advances, challenges, and perspectives

Cites Work

This page was built for publication: A dual ascent approach for steiner tree problems on a directed graph