Please use this identifier to cite or link to this item: https://olympias.lib.uoi.gr/jspui/handle/123456789/13194
Full metadata record
DC FieldValueLanguage
dc.contributor.authorArora, S.en
dc.contributor.authorKarakostas, G.en
dc.date.accessioned2015-11-24T17:26:23Z-
dc.date.available2015-11-24T17:26:23Z-
dc.identifier.issn0025-5610-
dc.identifier.urihttps://olympias.lib.uoi.gr/jspui/handle/123456789/13194-
dc.rightsDefault Licence-
dc.subjectk-minimum spanning treeen
dc.subjectapproximation algorithmen
dc.subjectprimal-dual schemaen
dc.subjecttreesen
dc.titleA 2+epsilon approximation algorithm for the k-MST problemen
heal.typejournalArticle-
heal.type.enJournal articleen
heal.type.elΆρθρο Περιοδικούel
heal.identifier.primaryDOI 10.1007/s10107-005-0693-1-
heal.identifier.secondary<Go to ISI>://000236418400008-
heal.identifier.secondaryhttp://download.springer.com/static/pdf/845/art%253A10.1007%252Fs10107-005-0693-1.pdf?auth66=1390991909_7814733229273a02cc2fd8c0bbcafb6d&ext=.pdf-
heal.languageen-
heal.accesscampus-
heal.recordProviderΠανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικώνel
heal.publicationDate2006-
heal.abstractFor any epsilon > 0 we give a (2 + epsilon)-approximation algorithm for the problem of finding a minimum tree spanning any k vertices in a graph (k-MST), improving a 3-approximation algorithm by Garg [10]. As in [10] the algorithm extends to a (2 + epsilon)-approximation algorithm for the minimum tour that visits any k vertices, provided the edge costs satisfy the triangle inequality.en
heal.journalNameMathematical Programmingen
heal.journalTypepeer reviewed-
heal.fullTextAvailabilityTRUE-
Appears in Collections:Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά)

Files in This Item:
File Description SizeFormat 
Arora-2006-A 2+epsilon approxim.pdf177.05 kBAdobe PDFView/Open    Request a copy


This item is licensed under a Creative Commons License Creative Commons