Afficher la notice abrégée

dc.contributor.authorAlfandari, Laurent
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2010-03-15T13:35:14Z
dc.date.available2010-03-15T13:35:14Z
dc.date.issued1999
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3688
dc.language.isoenen
dc.subjectSet coveringen
dc.subjectSpanning treeen
dc.subjectPolynomial approximationen
dc.subjectComplexityen
dc.subjectGraphen
dc.subject.ddc003en
dc.titleApproximating minimum spanning tree of depth 2en
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe 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.en
dc.relation.isversionofjnlnameInternational Transactions in Operational Research
dc.relation.isversionofjnlvol6en
dc.relation.isversionofjnlissue6en
dc.relation.isversionofjnldate1999
dc.relation.isversionofjnlpages607-622en
dc.relation.isversionofdoihttp://dx.doi.org/10.1111/j.1475-3995.1999.tb00176.xen
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherWileyen
dc.subject.ddclabelRecherche opérationnelleen


Fichiers attachés à cette notice

FichiersTailleFormatConsulter

Il n'y a pas de fichiers associés à cette notice.

Ce document fait partie de la (des) collection(s) suivante(s)

Afficher la notice abrégée