1. Repository of OAI
  2. ΑΠΟΘΕΤΗΡΙΟ "ΟΛΥΜΠΙΑΣ"
  3. Σχολή Θετικών Επιστημών
  4. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
  5. Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά)
Ελληνικά   English  
Please use this identifier to cite or link to this item: https://olympias.lib.uoi.gr/jspui/handle/123456789/10849
Full metadata record
DC FieldValueLanguage
dc.contributor.authorFragopoulou, P.en
dc.contributor.authorNikolopoulos, S. D.en
dc.contributor.authorPalios, L.en
dc.date.accessioned2015-11-24T17:00:59Z-
dc.date.available2015-11-24T17:00:59Z-
dc.identifier.issn0302-9743-
dc.identifier.urihttps://olympias.lib.uoi.gr/jspui/handle/123456789/10849-
dc.rightsDefault Licence-
dc.subjectmulti-source treesen
dc.subjecteccentricityen
dc.subjectweighted graphsen
dc.subjectnetworksen
dc.subjectcommunicationen
dc.subjectalgorithmsen
dc.subjectcomplexityen
dc.subjectspanning-treesen
dc.subjectcomplexityen
dc.titleMulti-source trees: Algorithms for minimizing eccentricity cost metricsen
heal.typejournalArticle-
heal.type.enJournal articleen
heal.type.elΆρθρο Περιοδικούel
heal.languageen-
heal.accesscampus-
heal.recordProviderΠανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικήςel
heal.publicationDate2005-
heal.abstractWe consider generalizations of the k-source sum of vertex eccentricity problem (k-SVET) and the k-source sum of source eccentricity problem (k-SSET) [1], which we call SDET and SSET, respectively, and provide efficient algorithms for their solution. The SDET (SSET, resp.) problem is defined as follows: given a weighted graph G and sets S of source nodes and D of destination nodes, which are subsets of the vertex set of G, construct a tree-subgraph T of G which connects all sources and destinations and minimizes the SDET cost function Sigma(d is an element of D) max(s is an element of S) d(T)(s, d) (the SSET cost function Sigma(s is an element of S) max(d is an element of D) dT(s, d), respectively). We describe an O(nm log n)-time algorithm for the SDET problem and thus, by symmetry, to the SSET problem, where n and m are the numbers of vertices and edges in G. The algorithm introduces efficient ways to identify candidates for the sought tree and to narrow down their number to O(m). Our algorithm readily implies O(nm log n)-time algorithms for the k-SVET and k-SSET problems as well.en
heal.journalNameAlgorithms and Computationen
heal.journalTypepeer reviewed-
heal.fullTextAvailabilityTRUE-
Appears in Collections:Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά)

Show simple item record
Files in This Item:
File Description SizeFormat 
nikolopoulos-2005-Multi-source trees Algorithms for minimizing eccentricity cost metrics.pdf406.98 kBAdobe PDFView/Open    Request a copy
Show simple item record  


This item is licensed under a Creative Commons License Creative Commons