Steiner trees in uniformly quasi-bipartite graphs.

DOI10.1016/S0020-0190(01)00335-0zbMath1043.68063OpenAlexW2033267048MaRDI QIDQ1853068

Hans Jürgen Prömel, Clemens Gröpl, Till Nierhoff, Stefan Hougardy

Publication date: 21 January 2003

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

Full work available at URL: https://doi.org/10.1016/s0020-0190(01)00335-0

zbMATH Keywords

Approximation algorithmsNetwork designAnalysis of algorithmsSteiner tree problem in graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (1)

Approximating Subdense Instances of Covering Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Steiner problem with edge lengths 1 and 2
• New approximation algorithms for the Steiner tree problems
• An analysis of the greedy algorithm for the submodular set covering problem
• An 11/6-approximation algorithm for the network Steiner problem
• Proof verification and the hardness of approximation problems
• A threshold of ln n for approximating set cover
• Improved Approximations for the Steiner Tree Problem
• A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3
• The computation of nearly minimal Steiner trees in graphs
• Steiner Minimal Trees

This page was built for publication: Steiner trees in uniformly quasi-bipartite graphs.