Multi-source trees: Algorithms for minimizing eccentricity cost metrics
Φόρτωση...
Ημερομηνία
Συγγραφείς
Fragopoulou, P.
Nikolopoulos, S. D.
Palios, L.
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Algorithms and Computation
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
We 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.
Περιγραφή
Λέξεις-κλειδιά
multi-source trees, eccentricity, weighted graphs, networks, communication, algorithms, complexity, spanning-trees, complexity
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής