• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Approximating minimum spanning tree of depth 2

Thumbnail
Date
1999
Dewey
Recherche opérationnelle
Sujet
Set covering; Spanning tree; Polynomial approximation; Complexity; Graph
Journal issue
International Transactions in Operational Research
Volume
6
Number
6
Publication date
1999
Article pages
607-622
Publisher
Wiley
DOI
http://dx.doi.org/10.1111/j.1475-3995.1999.tb00176.x
URI
https://basepub.dauphine.fr/handle/123456789/3688
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Alfandari, Laurent
Paschos, Vangelis
Type
Article accepté pour publication ou publié
Abstract (EN)
We prove that the problem of finding, in an undirected graph with non-negative costs on edges, a minimum cost rooted spanning tree of depth 2 is NP-hard. We then prove that, in a graph of order n, this problem cannot be approximated within better than O)lnn), unless problems in NP can be solved by slightly superpolynomial algorithms. We also prove that the metric version of the problem is MAX-SNP-hard and, consequently, cannot be approximated by polynomial time approximation schemes, unless P=NP. We devise approximation algorithms for several restricted cases and, finally, a polynomial time algorithm approximating the general problem within ratio lnn.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.