1,720,991 research outputs found
Hypergraph Traversal Revisited: Cost Measures and Dynamic Algorithms
No full textLecture Notes in Computer Science, Springer Verla
Fully dynamic all pairs shortest paths with real edge weights
No full textWe 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 deterministically in O(S · n2.5 log3 n) amortized time and queries in optimal worst-case time. No previous fully dynamic algorithm was known for this problem. In the special case where edge weights can only be increased, we give a randomized algorithm with one-sided error which supports updates faster in O (S · n log3 n) amortized time
Dynamically switching vertices in planar graphs
No full textWe consider graphs whose vertices may be in one of two different states: either on or off . We wish to maintain dynamically such graphs under an intermixed sequence of updates and queries. An update may reverse the status of a vertex, by switching it either on or off , and may insert a new edge or delete an existing edge. A query tests whether any two given vertices are connected in the subgraph induced by the vertices that are on . We give efficient algorithms that maintain information about connectivity on planar graphs in O( log3 n) amortized time per query, insert, delete, switch-on, and switch-off operation over sequences of at least Ω(n) operations, where n is the number of vertices of the graph
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
Predicting deadlock in store-and-forward networks
No full textAim of this paper is to study the complexity of the Deadlock-Safety problem for Store-and-Forward networks. The following results are shown: 1. the problem is in general NP-complete, even for tree-like networks. It is still NP-complete for various "simple" topologies (including bipartite, grid and two-terminals series-parallel graphs) when each vertex buffer is of unit capacity; 2. the problem is solvable in PTIME for 1-buffer tree-like networks
- …
