Worst-case performance of Wong's Steiner tree heuristic

DOI10.1016/J.DAM.2005.05.027zbMATH Open1120.90045OpenAlexW2045031547MaRDI QIDQ2489899FDOQ2489899

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

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

zbMATH Keywords

Steiner problemApproximation algorithmsWorst-case performanceWong's heuristic

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Optimum branchings
• Title not available (Why is that?)
• A series of approximation algorithms for the acyclic directed Steiner tree problem
• The Steiner tree problem
• Steiner problem in networks: A survey
• A Dual-Based Procedure for Uncapacitated Facility Location
• Improved algorithms for the Steiner problem in networks
• A dual ascent approach for steiner tree problems on a directed graph
• Title not available (Why is that?)
• A hybrid GRASP with perturbations for the Steiner problem in graphs
• A fast algorithm for Steiner trees
• Title not available (Why is that?)
• A catalog of steiner tree formulations
• An improved approximation scheme for the Group Steiner Problem
• Dual heuristics on the exact solution of large Steiner problems
• Title not available (Why is that?)
• The primal-dual method for approximation algorithms
• A Comparison of Two Simulated Annealing Algorithms Applied to the Directed Steiner Problem on Networks
• An approach for the Steiner problem in directed graphs
• Directed Steiner Tree Problem On A Graph: Models, Relaxations And Algorithms
• A lower bound for the steiner tree problem in directed graphs
• Reactive tabu search with path-relinking for the Steiner problem in graphs
• 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)