Skip to Main content Skip to Navigation
Reports

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

https://hal-supelec.archives-ouvertes.fr/hal-00793424
Contributor : Marc-Antoine Weisser <>
Submitted on : Friday, February 22, 2013 - 12:11:32 PM
Last modification on : Monday, December 14, 2020 - 12:38:06 PM
Long-term archiving on: : Sunday, April 2, 2017 - 4:20:50 AM

File

planarcasinapprox.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00793424, version 1

Citation

Dimitri Watel, Marc-Antoine Weisser, Cédric Bentz. Inapproximability proof of DSTLB and USTLB in planar graphs. 2013. ⟨hal-00793424v1⟩

Share

Metrics

Record views

36

Files downloads

7