The Steiner tree problem on graphs: inapproximability results
DOI10.1016/j.tcs.2008.06.046zbMath1160.68023OpenAlexW2027515293WikidataQ55952584 ScholiaQ55952584MaRDI QIDQ952442
Miroslav Chlebík, Janka Chlebíková
Publication date: 12 November 2008
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://researchportal.port.ac.uk/portal/en/publications/the-steiner-tree-problem-on-graphs-inapproximability-results(5f4546f2-09e3-499a-af6a-7b7013a601b6).html
Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (34)
Cites Work
- Ramanujan graphs
- The Steiner problem with edge lengths 1 and 2
- Asymptotically optimal switching circuits
- Explicit constructions of linear-sized superconcentrators
- On the approximability of the Steiner tree problem.
- On the approximability of the traveling salesman problem (extended abstract)
- On Concentrators, Superconcentrators, Generalizers, and Nonblocking Networks
- Some optimal inapproximability results
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: The Steiner tree problem on graphs: inapproximability results