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.
Type de document :
Rapport
[Research Report] Supélec. 2013
Liste complète des métadonnées

Littérature citée [2 références]  Voir  Masquer  Télécharger

https://hal-supelec.archives-ouvertes.fr/hal-00793424
Contributeur : Marc-Antoine Weisser <>
Soumis le : lundi 25 février 2013 - 11:24:00
Dernière modification le : samedi 9 février 2019 - 01:23:03
Document(s) archivé(s) le : dimanche 2 avril 2017 - 04:55:28

Fichier

planarcasinapprox.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00793424, version 2

Collections

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〉

Partager

Métriques

Consultations de la notice

250

Téléchargements de fichiers

97