Inapproximability proof of DSTLB and USTLB in planar graphs

Abstract : This document proves the problem of finding a minimum cost Steiner Tree covering k terminals with at most p branching nodes (with outdegree greater than 1), in a directed or an undirected planar graph with n nodes, is hard to approximate within a better ratio than n, even when the parameter p is fixed.
Document type :
Reports
Complete list of metadatas

Cited literature [2 references]  Display  Hide  Download

https://hal-supelec.archives-ouvertes.fr/hal-00793424
Contributor : Marc-Antoine Weisser <>
Submitted on : Monday, February 25, 2013 - 11:24:00 AM
Last modification on : Saturday, February 9, 2019 - 1:23:03 AM
Long-term archiving on : Sunday, April 2, 2017 - 4:55:28 AM

File

planarcasinapprox.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00793424, version 2

Citation

Dimitri Watel, Marc-Antoine Weisser, Cédric Bentz. Inapproximability proof of DSTLB and USTLB in planar graphs. [Research Report] Supélec. 2013. ⟨hal-00793424v2⟩

Share

Metrics

Record views

253

Files downloads

106