scientific article; zbMATH DE number 2089220

MaRDI QIDQ3046489zbMATH OpenFDO

Authors Miroslav Chlebík, Janka Chlebíková

Publication date 12 August 2004

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2368/23680170.htm

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The Steiner tree problem on graphs: inapproximability results
• On the approximability of the Steiner tree problem.
• scientific article; zbMATH DE number 1834686
• scientific article; zbMATH DE number 1445376
• On the hardness of full Steiner tree problems

Cited in

(31)

• Packing trees in communication networks
• Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation
• On approximation algorithms for the terminal Steiner tree problem
• On the approximability of the Steiner tree problem.
• Differential approximation results for the Steiner tree problem
• A robust and scalable algorithm for the Steiner problem in graphs
• The internal Steiner tree problem: Hardness and approximations
• A new approximation algorithm for the selective single-sink buy-at-bulk problem in network design
• Complexity of approximating bounded variants of optimization problems
• Hardness and approximation results for packing Steiner trees
• Parameterized approximation schemes for Steiner trees with small number of Steiner vertices
• A $$(1+{\varepsilon })$$ ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
• On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree
• On the approximability of dense Steiner problems
• scientific article; zbMATH DE number 219235 (Why is no real title available?)
• scientific article; zbMATH DE number 1834686 (Why is no real title available?)
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• Single-sink fractionally subadditive network design
• A Faster Shortest-Paths Algorithm for Minor-Closed Graph Classes
• A (1+\varepsilon)-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
• Hardness of Approximation Results for the Problem of Finding the Stopping Distance in Tanner Graphs
• scientific article; zbMATH DE number 5042868 (Why is no real title available?)
• scientific article; zbMATH DE number 7053371 (Why is no real title available?)
• Parameterized approximation schemes for Steiner trees with small number of Steiner vertices
• Stronger path‐based extended formulation for the Steiner tree problem
• Robust Algorithms for TSP and Steiner Tree
• On approximability of Steiner tree in \(\ell_p\)-metrics
• Robust algorithms for TSP and Steiner tree
• Approximation algorithms for general packing problems and their application to the multicast congestion problem
• On routing in VLSI design and communication networks
• The Steiner tree problem on graphs: inapproximability results

This page was built for publication:

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