CINECA IRIS Institutional Research Information System
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishWe consider a two-edge connected, non-negatively real-weighted graph G with n vertices and m edges, and a single-source shortest paths tree (SPT) of G rooted at an arbitrary vertex. If an edge of the SPT is temporarily removed, a widely recognized approach to reconnect the vertices disconnected from the root consists of joining the two resulting subtrees by means of a single non-tree edge, called a swap edge. This allows to reduce consistently the set-up and computational costs which are incurred if one instead rebuilds a new optimal SPT from scratch. In the past, several optimality criteria have been considered to select a best possible swap edge, and here we restrict our attention to arguably the two most significant measures: the minimization of either the maximum or the average distance between the root and the disconnected vertices. For the former criteria, we present an O(mlogα(m,n)) time algorithm—where α is the inverse of the Ackermann function—to find a best swap edge for every edge of the SPT, thus improving onto the previous O(mlogn) time algorithm. Concerning the latter criteria, we provide an O(m+nlogn) time algorithm for the special but important case where G is unweighted, which compares favourably with the O(m+nα(n,n)log2n) time bound that one would get by using the fastest algorithm known for the weighted case—once this is suitably adapted to the unweighted case.
A faster computation of all the best swap edges of a shortest paths tree / BILO' D; GUALÀ LUCIANO; PROIETTI GUIDO. - In: ALGORITHMICA. - ISSN 0178-4617. - 73:3(2015), pp. 547-570. [10.1007/s00453-014-9912-6]
Scheda prodotto non validato
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo
| Titolo: | A faster computation of all the best swap edges of a shortest paths tree | |
| Autori: | ||
| Data di pubblicazione: | 2015 | |
| Rivista: | ||
| Citazione: | A faster computation of all the best swap edges of a shortest paths tree / BILO' D; GUALÀ LUCIANO; PROIETTI GUIDO. - In: ALGORITHMICA. - ISSN 0178-4617. - 73:3(2015), pp. 547-570. [10.1007/s00453-014-9912-6] | |
| Handle: | http://hdl.handle.net/11388/59746 | |
| Appare nelle tipologie: | 1.1 Articolo in rivista |
File in questo prodotto:
http://hdl.handle.net/11388/59746
Copyright © 2022