169,925 research outputs found
Experimental Analysis of Dynamic All Pairs Shortest Path Algorithms
No full textWe present the results of an extensive computational study on dynamic algorithms for all pairs shortest path problems. We describe our implementations of the recent dynamic algorithms of King [1999] and of Demetrescu and Italiano [2006], and compare them to the dynamic algorithm of Ramalingam and Reps and to static algorithms on random, real-world and hard instances. Our experimental data suggest that some of the dynamic algorithms and their algorithmic techniques can be really of practical value in many situations
Mantaining dynamic matrices for fully dynamic transitive closure
No full textIn this paper we introduce a general framework for casting fully dynamic transitive closure into the problem of reevaluating polynomials over matrices. With this technique, we improve the best known bounds for fully dynamic transitive closure. In particular, we devise a deterministic algorithm for general directed graphs that achieves O(n(2)) amortized time for updates, while preserving unit worst-case cost for queries. In case of deletions only, our algorithm performs updates faster in O(n) amortized time. We observe that fully dynamic transitive closure algorithms with O(1) query time maintain explicitly the transitive closure of the input graph, in order to answer each query with exactly one lookup (on its adjacency matrix). Since an update may change as many as Omega(n(2)) entries of this matrix, no better bounds are possible for this class of algorithms
A new approach to dynamic all pairs shortest paths
No full textWe study novel combinatorial properties of graphs that allow us to devise a completely new approach to dynamic all pairs shortest paths problems. Our approach yields a fully dynamic algorithm for general directed graphs with non-negative realvalued edge weights that supports any sequence of operations in O(n time per update and unit worst-case time per distance query, where n is the number of vertices. We can also report shortest paths in optimal worst-case time. These bounds improve substantially over previous results and solve a long-standing open problem. Ou
On bibliometrics in academic promotions: a case study in computer science and engineering in Italy
No full textDue to its quantitative nature, bibliometrics is becoming increasingly popular among policy makers for academic hiring and career promotions. In this article, we quantitatively assess the impact that the granularity level in the classification of scientific areas would entail on research evaluation based on bibliometric indicators. We use as a case study the Italian national habilitation system (ASN), which classifies faculty members according to their academic discipline and relies on journal counts, citations, and h-indices as a basis for promoting tenure track researchers to associate professors and associate to full professors. The assessment checks whether the individual indicators of a researcher are above a certain threshold, e.g., the median over the population of researchers working in the same discipline.
Our investigation focuses on two related, rather broad disciplines: computer science and computer engineering. We show that the ASN practice of using the same thresholds for all members of a scientific discipline can favor certain sub-communities that are characterized by higher bibliometric indicators, and disfavor others. We report evidence that up to 30% of Italian faculty members of certain sub-communities would see their indicators drop below the threshold, thus becoming not eligible for promotion, if the ASN were conducted on a more accurate, fine-grained classification. Conversely, in the same scenario, up to 11% of faculty members, in different sub-communities, would see their indicators rise above the threshold, granting them eligibility. Our data set includes 1,685 authors, 89,185 distinct publications, and 262,286 author- publication pairs
Algorithmic techniques for maintaining shortest routes in dynamic networks
No full textIn this paper, we survey algorithms for shortest paths in dynamic networks. Although research on this problem spans over more than three decades, in the last couple of years many novel algorithmic techniques have been proposed. In this survey, we will make a special effort to abstract some combinatorial and algebraic properties, and some common data-structural tools that are at the base of those techniques. This will help us try to present some of the newest results in a unifying framework so that they can be better understood and deployed also by non-specialists. © 2007 Elsevier B.V. All rights reserved
Fully dynamic all pairs shortest paths with real edge weights
No full textAbstractWe present the first fully dynamic algorithm for maintaining all pairs shortest paths in directed graphs with real-valued edge weights. Given a dynamic directed graph G such that each edge can assume at most S different real values, we show how to support updates in O(n2.5Slog3n) amortized time and queries in optimal worst-case time. This algorithm is deterministic: no previous fully dynamic algorithm was known before for this problem. In the special case where edge weights can only be increased, we give a randomized algorithm with one-sided error that supports updates faster in O(S⋅nlog3n) amortized time. We also show how to obtain query/update trade-offs for this problem, by introducing two new families of randomized algorithms. Algorithms in the first family achieve an update bound of O˜(S⋅k⋅n2)1 and a query bound of O˜(n/k), and improve over the previous best known update bounds for k in the range (n/S)1/3⩽k<(n/S)1/2. Algorithms in the second family achieve an update bound of O˜(S⋅k⋅n2) and a query bound of O˜(n2/k2), and are competitive with the previous best known update bounds (first family included) for k in the range (n/S)1/6⩽k<(n/S)1/3
Algoritmi e strutture dati (seconda edizione)
No full textQuesto libro offre un'introduzione allo studio degli algoritmi e delle strutture dati, cercando di conciliare comprensibilità, chiarezza di esposizione e rigore matematico. Particolare enfasi è posta sull'astrazione delle tecniche e delle metodologie generali di progetto e analisi di algoritmi, stimolandone la comprensione intuitiva dei principi fondamentali. Il libro è concepito soprattutto per corsi universitari delle facoltà di ingegneria e di scienze matematiche, fisiche e naturali. Il testo, pur essendo indipendente dalla scelta di un particolare linguaggio di programmazione, adotta un approccio orientato agli oggetti sia nella descrizione delle strutture dati che nello pseudocodice utilizzato per descrivere gli algoritmi. In tal modo, pur astraendo dai dettagli implementativi di basso livello, gli algoritmi presentati non risultano troppo distanti da una loro reale implementazione
- …
