Worst-case performance of Wong's Steiner tree heuristic

DOI10.1016/j.dam.2005.05.027zbMath1120.90045OpenAlexW2045031547MaRDI QIDQ2489899

Alfredo Candia-Véjar, Hugo Bravo-Azlán

Publication date: 28 April 2006

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2005.05.027

zbMATH Keywords

Steiner problemApproximation algorithmsWorst-case performanceWong's heuristic

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (1)

Solving Steiner trees: Recent advances, challenges, and perspectives

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A series of approximation algorithms for the acyclic directed Steiner tree problem
• A fast algorithm for Steiner trees
• An approach for the Steiner problem in directed graphs
• The Steiner tree problem
• Worst-case performance of some heuristics for Steiner's problem in directed graphs
• The primal-dual method for approximation algorithms
• An improved approximation scheme for the Group Steiner Problem
• A Hybrid GRASP with Perturbations for the Steiner Problem in Graphs
• A dual ascent approach for steiner tree problems on a directed graph
• Steiner problem in networks: A survey
• A Dual-Based Procedure for Uncapacitated Facility Location
• A Comparison of Two Simulated Annealing Algorithms Applied to the Directed Steiner Problem on Networks
• Directed Steiner Tree Problem On A Graph: Models, Relaxations And Algorithms
• A catalog of steiner tree formulations
• Optimum branchings
• A lower bound for the steiner tree problem in directed graphs
• Improved algorithms for the Steiner problem in networks

This page was built for publication: Worst-case performance of Wong's Steiner tree heuristic