On Rajagopalan and Vazirani's 32e-approximation bound for the iterated 1-Steiner heuristic

DOI10.1016/S0020-0190(03)00210-2zbMATH Open1173.68868DBLPjournals/ipl/Rizzi03WikidataQ29036224 ScholiaQ29036224MaRDI QIDQ1007642FDOQ1007642

Romeo Rizzi

Publication date: 23 March 2009

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

local searchapproximation algorithmsSteiner treebit scalingiterated 1-Steiner heuristic

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (3)

• New geometry-inspired relaxations and algorithms for the metric Steiner tree problem
• A partition-based relaxation for Steiner trees
• Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs

   Recommendations

• Title not available (Why is that?) 👍 👎
• Tighter Bounds for Graph Steiner Tree Approximation 👍 👎
• A partition-based relaxation for Steiner trees 👍 👎
• Title not available (Why is that?) 👍 👎
• A faster approximation algorithm for the Steiner problem in graphs 👍 👎

This page was built for publication: On Rajagopalan and Vazirani's \(\frac{3}{2}e\)-approximation bound for the iterated 1-Steiner heuristic

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