scientific article; zbMATH DE number 1305468

zbMath0938.68072MaRDI QIDQ4252355

Sridhar Rajagopalan, Vijay V. Vazirani

Publication date: 17 June 1999

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

metric Steiner tree problemquasi-bipartite graphs

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (20)

On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree ⋮ New primal-dual algorithms for Steiner tree problems ⋮ Some results on spanning trees ⋮ On imposing connectivity constraints in integer programs ⋮ Stronger path‐based extended formulation for the Steiner tree problem ⋮ A linear programming based approach to the Steiner tree problem with a fixed number of terminals ⋮ On the Price of Stability of Undirected Multicast Games ⋮ Combination algorithms for Steiner tree variants ⋮ New geometry-inspired relaxations and algorithms for the metric Steiner tree problem ⋮ Approximation algorithms for metric tree cover and generalized tour and tree covers ⋮ Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs ⋮ A partition-based relaxation for Steiner trees ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs ⋮ On Rajagopalan and Vazirani's \(\frac{3}{2}e\)-approximation bound for the iterated 1-Steiner heuristic ⋮ Approaches to the Steiner Problem in Networks ⋮ Recent results on approximating the Steiner tree problem and its generalizations ⋮ Steiner trees in uniformly quasi-bipartite graphs. ⋮ On approximability of the independent/connected edge dominating set problems ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs ⋮ Multi-rooted greedy approximation of directed Steiner trees with applications

This page was built for publication: