Steiner trees in uniformly quasi-bipartite graphs.
type: Item
instance of: scholarly article
title: Steiner trees in uniformly quasi-bipartite graphs.
zbMATH Open document ID: 1043.68063
DOI: 10.1016/S0020-0190(01)00335-0
author: Clemens Gröpl
author: Stefan Hougardy
author: Till Nierhoff
author: Hans Jürgen Prömel
published in: Information Processing Letters
publication date: 2003-01-21T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68W40
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 1856409
zbMATH Keywords: Analysis of algorithms
zbMATH Keywords: Approximation algorithms
zbMATH Keywords: Network design
zbMATH Keywords: Steiner tree problem in graphs
MaRDI profile type: Publication
cites work: Proof verification and the hardness of approximation problems
cites work: Improved Approximations for the Steiner Tree Problem
cites work: The Steiner problem with edge lengths 1 and 2
cites work: A threshold of ln n for approximating set cover
cites work: Steiner Minimal Trees
cites work: Q4448761
cites work: Q4252319
cites work: Q4142699
cites work: New approximation algorithms for the Steiner tree problems
cites work: A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3
cites work: Q4252355
cites work: The computation of nearly minimal Steiner trees in graphs
cites work: Q4952699
cites work: Q4779183
cites work: An analysis of the greedy algorithm for the submodular set covering problem
cites work: An 11/6-approximation algorithm for the network Steiner problem
full work available at URL: s0020-0190(01)00335-0
OpenAlex ID: W2033267048
Recommended article: Steiner trees in general nonuniform orientations
Recommended article: An inequality on Steiner trees
Recommended article: Steiner tree in \(k\)-star caterpillar convex bipartite graphs: a dichotomy
Recommended article: On Steiner trees and minimum spanning trees in hypergraphs
Recommended article: On full Steiner trees in unit disk graphs
Recommended article: Q4945798
Recommended article: On the location of Steiner points in uniformly-oriented Steiner trees.
Recommended article: The Steiner tree problem on graphs: inapproximability results
Recommended article: Bifurcations of Steiner tree topologies in the plane
Recommended article: Binary Steiner trees: structural results and an exact solution approach
description: scientific article; zbMATH DE number 1856409