scientific article; zbMATH DE number 2089220

zbMATH Open1078.68637MaRDI QIDQ3046489FDOQ3046489

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

Title of this publication is not available (Why is that?)

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

Mathematics Subject Classification ID

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

Cited In (30)

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

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)