 |
ECOLE SUPÉRIEURE D'ÉLECTRICITÉ Une grande école d'ingénieurs au cœur des sciences de l'information,de l'énergie et des systèmes |
 |
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.
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
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)