Worst-case performance of Wong's Steiner tree heuristic

DOI10.1016/J.DAM.2005.05.027MaRDI QIDQ2489899zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Worst-case performance of some heuristics for Steiner's problem in directed graphs
• Publication:4934235
• scientific article; zbMATH DE number 32742
• Performance Oriented Spanning Trees
• A tight worst case bound for the performance ratio of heuristics for the minimum rectilinear Steiner tree problem

Cites work

• scientific article; zbMATH DE number 4010182 (Why is no real title available?)
• scientific article; zbMATH DE number 3677874 (Why is no real title available?)
• scientific article; zbMATH DE number 3568354 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3285076 (Why is no real title available?)
• A Comparison of Two Simulated Annealing Algorithms Applied to the Directed Steiner Problem on Networks
• A Dual-Based Procedure for Uncapacitated Facility Location
• A catalog of steiner tree formulations
• A dual ascent approach for steiner tree problems on a directed graph
• A fast algorithm for Steiner trees
• A hybrid GRASP with perturbations for the Steiner problem in graphs
• A lower bound for the steiner tree problem in directed graphs
• A series of approximation algorithms for the acyclic directed Steiner tree problem
• An approach for the Steiner problem in directed graphs
• An improved approximation scheme for the Group Steiner Problem
• Directed Steiner Tree Problem On A Graph: Models, Relaxations And Algorithms
• Dual heuristics on the exact solution of large Steiner problems
• Improved algorithms for the Steiner problem in networks
• Optimum branchings
• Reactive tabu search with path-relinking for the Steiner problem in graphs
• Steiner problem in networks: A survey
• The Steiner tree problem
• The primal-dual method for approximation algorithms
• Worst-case performance of some heuristics for Steiner's problem in directed graphs

Cited in

(1)

• Solving Steiner trees: Recent advances, challenges, and perspectives

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

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