126,031 research outputs found
Finding strong articulation points and strong bridges in linear time
No full textGiven a directed graph G, an edge is a strong bridge if its removal increases the number of strongly connected components of G. Similarly, we say that a vertex is a strong articulation point if its removal increases the number of strongly connected components of G. In this paper, we present linear-time algorithms for computing all the strong bridges and all the strong articulation points of directed graphs, solving an open problem posed in Beldiceanu et al. (2005)
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
On Resilient Graph Spanners
No full textWe introduce and investigate a new notion of resilience in graph spanners. Let S be a spanner of a weighted graph G. Roughly speaking, we say that S is resilient if all its point- to-point distances are resilient to edge failures. Namely, whenever any edge in G fails, then as a consequence of this failure all distances do not degrade in S substantially more than in G (i.e., the relative distance increases in S are very close to those in the underlying graph G). In this paper we show that sparse resilient spanners exist, and that they can be computed efficiently
La historiografía sobre el desarrollo económico italiano en los últimos treinta años
No full textEditada en la Universidad Carlos IIIEste ensayo analiza la historiografía del crecimiento económico italiano
moderno, distinguiendo entre los enfoques que consideran a Italia como un
caso más en el proceso general de industrialización europea y aquellos que
identifican unas características específicas y únicas del caso italiano. Se pasa
revista también en este trabajo a los intentos de hallar una cronología del
desarrollo en Italia y de establecer sus causas y condiciones.This essays analyzes the historiography of Italy's modern economic growth.
A distinction is made between those interpretations that emphasize the uniqueness
of the Italian experience and those that include Italy in the general process
that started in Britain and spread to the rest of Europe through the nineteenth
and twentieth centuries. In addition, the article surveys the most recent attempts
to establish the timing, the causes, and the obstacles to Italy's economic
growth during the last century.Publicad
Approccio sperimentale per l'interpretazione del ruolo fisiologico degli autacoidi di origine endoteliale
No full textFully 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
Small stretch (alpha, beta)-spanners in the streaming model
No full textWe present algorithms for computing small stretch (α, β)-spanners in the streaming model. An (α, β)-spanner of a graph G is a subgraph S ⊆ G such that for each pair of vertices the distance in S is at most α times the distance in G plus β. We assume that the graph is given as a stream of edges and vertices, and that only one pass over the data is allowed. Furthermore, the number of vertices and edges are not known in advance. We denote by m the current number of scanned edges and by n the current number of discovered vertices. In this model we show how to compute a (k, k - 1)-spanner of an unweighted undirected graph, for k = 2, 3, in O (1) amortized processing time per edge/vertex. The computed (k, k - 1)-spanners have O (n1 + 1 / k) edges and our algorithms use only O (n1 + 1 / k) words of memory space. In case only Θ (n) internal memory is available, the same spanners can be computed using O (n1 + 1 / k / B) external memory blocks, each of size B. Each edge/vertex is processed in O (1) amortized time, plus O (1 / B) amortized block transfers. © 2008 Elsevier B.V. All rights reserved
On line algorithms for polynomially solvable satisfiability problems
No full textAbstractGiven a propositional Horn formula, we show how to maintain on-line information about its satisfiability during the insertion of new clauses. A data structure is presented which answers each satisfiability question in O(1) time and inserts a new clause of length q in O(q) amortized time. This significantly outperforms previously known solutions of the same problem. This result is extended also to a particular class of non-Horn formulae already considered in the literature, for which the space bound is improved. Other operations are considered, such as testing whether a given hypothesis is consistent with a satisfying interpretation of the given formula and determining a truth assignment which satisfies a given formula. The on-line time and space complexity of these operations is also analyzed
- …
