Página 1 dos resultados de 658 itens digitais encontrados em 0.004 segundos

Ranking multiobjective shortest paths

Martins, Ernesto Queirós; Paixão, José Manuel; Rosa, Mário Silva; Santos, José Luis
Fonte: Centro de Matemática da Universidade de Coimbra Publicador: Centro de Matemática da Universidade de Coimbra
Tipo: Pré-impressão
ENG
Relevância na Pesquisa
46.7%
This paper is concerned with the ranking of multi-objective shortest paths accordingly to an order relation verifying certain conditions such is the case, for instance, of the lexicographic order. We present a new labelling algorithm that makes use of shortest deviation paths for obtaining the set of Pareto solutions for the multi-objective shortest path problem. The computational experience reported at the end of the paper shows that the new algorithm clearly outperforms the previous approaches when one looks for the `-th shortest non-dominated paths.; FCT, POCTI - Research Units Pluriannual Funding to Centro de Matemática da Universidade de Coimbra, CIO (Operations Research Center of the University of Lisbon); POCTI/MAT/139/2001 cofunded by the EU program FEDER.

K-menores caminhos; k-shortest paths

Pisaruk, Fabio
Fonte: Biblioteca Digitais de Teses e Dissertações da USP Publicador: Biblioteca Digitais de Teses e Dissertações da USP
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 16/06/2009 PT
Relevância na Pesquisa
56.81%
Tratamos da generalização do problema da geração de caminho mínimo, no qual não apenas um, mas vários caminhos de menores custos devem ser produzidos. O problema dos k-menores caminhos consiste em listar os k caminhos de menores custos conectando um par de vértices. Esta dissertação trata de algoritmos para geração de k-menores caminhos em grafos simétricos com custos não-negativos, bem como algumas implementações destes.; We consider a long-studied generalization of the shortest path problem, in which not one but several short paths must be produced. The k-shortest (simple) paths problem is to list the k paths connecting a given source-destination pair in the digraph with minimum total length. This dissertation deals with k-shortest simple paths algorithms designed for nonnegative costs, undirected graphs and some implementations of them.

Shortest Paths, Network Design and Associated Polyhedra

Magnanti, Thomas L.; Mirchandani, Prakash
Fonte: Massachusetts Institute of Technology, Operations Research Center Publicador: Massachusetts Institute of Technology, Operations Research Center
Tipo: Trabalho em Andamento Formato: 2526212 bytes; application/pdf
EN_US
Relevância na Pesquisa
56.55%
We study a specialized version of network design problems that arise in telecommunication, transportation and other industries. The problem, a generalization of the shortest path problem, is defined on an undirected network consisting of a set of arcs on which we can install (load), at a cost, a choice of up to three types of capacitated facilities. Our objective is to determine the configuration of facilities to load on each arc that will satisfy the demand of a single commodity at the lowest possible cost. Our results (i) demonstrate that the single-facility loading problem and certain "common breakeven point" versions of the two-facility and three-facility loading problems are polynomially solvable as a shortest path problem; (ii) show that versions of the twofacility loading problem are strongly NP-hard, but that a shortest path solution provides an asymptotically "good" heuristic; and (iii) characterize the optimal solution (that is, specify a linear programming formulation with integer solutions) of the common breakeven point versions of the two-facility and three-facility loading problems. In this development, we introduce two new families of facets, give geometric interpretations of our results, and demonstrate the usefulness of partitioning the space of the problem parameters to establish polyhedral integrality properties. Generalizations of our results apply to (i) multicommodity applications and (ii) situations with more than three facilities.

Shortest Paths with Pairwise-Distinct Edge Labels: Finding Biochemical Pathways in Metabolic Networks

Fekete, Sandor; Kamphans, Tom; Stelzer, Michael
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 22/12/2010
Relevância na Pesquisa
46.72%
A problem studied in Systems Biology is how to find shortest paths in metabolic networks. Unfortunately, simple (i.e., graph theoretic) shortest paths do not properly reflect biochemical facts. An approach to overcome this issue is to use edge labels and search for paths with distinct labels. In this paper, we show that such biologically feasible shortest paths are hard to compute. Moreover, we present solutions to find such paths in networks in reasonable time.; Comment: 9 pages, 5 figures

Two betweenness centrality measures based on Randomized Shortest Paths

Kivimäki, Ilkka; Lebichot, Bertrand; Saramäki, Jari; Saerens, Marco
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 10/09/2015
Relevância na Pesquisa
46.78%
This paper introduces two new closely related betweenness centrality measures based on the Randomized Shortest Paths (RSP) framework, which fill a gap between traditional network centrality measures based on shortest paths and more recent methods considering random walks or current flows. The framework defines Boltzmann probability distributions over paths of the network which focus on the shortest paths, but also take into account longer paths depending on an inverse temperature parameter. RSP's have previously proven to be useful in defining distance measures on networks. In this work we study their utility in quantifying the importance of the nodes of a network. The proposed RSP betweenness centralities combine, in an optimal way, the ideas of using the shortest and purely random paths for analysing the roles of network nodes, avoiding issues involving these two paradigms. We present the derivations of these measures and how they can be computed in an efficient way. In addition, we show with real world examples the potential of the RSP betweenness centralities in identifying interesting nodes of a network that more traditional methods might fail to notice.

Combining the Shortest Paths and the Bottleneck Paths Problems

Shinn, Tong-Wook; Takaoka, Tadao
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 20/11/2013
Relevância na Pesquisa
46.78%
We combine the well known Shortest Paths (SP) problem and the Bottleneck Paths (BP) problem to introduce a new problem called the Shortest Paths for All Flows (SP-AF) problem that has relevance in real life applications. We first solve the Single Source Shortest Paths for All Flows (SSSP-AF) problem on directed graphs with unit edge costs in $O(mn)$ worst case time bound. We then present two algorithms to solve SSSP-AF on directed graphs with integer edge costs bounded by $c$ in $O(m^2 + nc)$ and $O(m^2 + mn\log{(\frac{c}{m})})$ time bounds. Finally we extend our algorithms for the SSSP-AF problem to solve the All Pairs Shortest Paths for All Flows (APSP-AF) problem in $O(m^{2}n + nc)$ and $O(m^{2}n + mn^{2}\log{(\frac{c}{mn})})$ time bounds. All algorithms presented in this paper are practical for implementation.; Comment: Will be presented at ACSC 2014

Combining All Pairs Shortest Paths and All Pairs Bottleneck Paths Problems

Shinn, Tong-Wook; Takaoka, Tadao
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 22/09/2013
Relevância na Pesquisa
46.72%
We introduce a new problem that combines the well known All Pairs Shortest Paths (APSP) problem and the All Pairs Bottleneck Paths (APBP) problem to compute the shortest paths for all pairs of vertices for all possible flow amounts. We call this new problem the All Pairs Shortest Paths for All Flows (APSP-AF) problem. We firstly solve the APSP-AF problem on directed graphs with unit edge costs and real edge capacities in $\tilde{O}(\sqrt{t}n^{(\omega+9)/4}) = \tilde{O}(\sqrt{t}n^{2.843})$ time, where $n$ is the number of vertices, $t$ is the number of distinct edge capacities (flow amounts) and $O(n^{\omega}) < O(n^{2.373})$ is the time taken to multiply two $n$-by-$n$ matrices over a ring. Secondly we extend the problem to graphs with positive integer edge costs and present an algorithm with $\tilde{O}(\sqrt{t}c^{(\omega+5)/4}n^{(\omega+9)/4}) = \tilde{O}(\sqrt{t}c^{1.843}n^{2.843})$ worst case time complexity, where $c$ is the upper bound on edge costs.

Computing shortest paths in 2D and 3D memristive networks

Ye, Zhanyou; Wu, Shi Hong Marcus; Prodromakis, Themistoklis
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 15/03/2013
Relevância na Pesquisa
46.67%
Global optimisation problems in networks often require shortest path length computations to determine the most efficient route. The simplest and most common problem with a shortest path solution is perhaps that of a traditional labyrinth or maze with a single entrance and exit. Many techniques and algorithms have been derived to solve mazes, which often tend to be computationally demanding, especially as the size of maze and number of paths increase. In addition, they are not suitable for performing multiple shortest path computations in mazes with multiple entrance and exit points. Mazes have been proposed to be solved using memristive networks and in this paper we extend the idea to show how networks of memristive elements can be utilised to solve multiple shortest paths in a single network. We also show simulations using memristive circuit elements that demonstrate shortest path computations in both 2D and 3D networks, which could have potential applications in various fields.

Maximum st-flow in directed planar graphs via shortest paths

Borradaile, Glencora; Harutyunyan, Anna
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 24/05/2013
Relevância na Pesquisa
46.65%
Minimum cuts have been closely related to shortest paths in planar graphs via planar duality - so long as the graphs are undirected. Even maximum flows are closely related to shortest paths for the same reason - so long as the source and the sink are on a common face. In this paper, we give a correspondence between maximum flows and shortest paths via duality in directed planar graphs with no constraints on the source and sink. We believe this a promising avenue for developing algorithms that are more practical than the current asymptotically best algorithms for maximum st-flow.; Comment: 20 pages, 4 figures. Short version to be published in proceedings of IWOCA'13

Shortest Paths in Less Than a Millisecond

Agarwal, Rachit; Caesar, Matthew; Godfrey, P. Brighten; Zhao, Ben Y.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 06/06/2012
Relevância na Pesquisa
46.64%
We consider the problem of answering point-to-point shortest path queries on massive social networks. The goal is to answer queries within tens of milliseconds while minimizing the memory requirements. We present a technique that achieves this goal for an extremely large fraction of path queries by exploiting the structure of the social networks. Using evaluations on real-world datasets, we argue that our technique offers a unique trade-off between latency, memory and accuracy. For instance, for the LiveJournal social network (roughly 5 million nodes and 69 million edges), our technique can answer 99.9% of the queries in less than a millisecond. In comparison to storing all pair shortest paths, our technique requires at least 550x less memory; the average query time is roughly 365 microseconds --- 430x faster than the state-of-the-art shortest path algorithm. Furthermore, the relative performance of our technique improves with the size (and density) of the network. For the Orkut social network (3 million nodes and 220 million edges), for instance, our technique is roughly 2588x faster than the state-of-the-art algorithm for computing shortest paths.; Comment: 6 pages; to appear in SIGCOMM WOSN 2012

Fully Dynamic All Pairs All Shortest Paths

Pontecorvi, Matteo; Ramachandran, Vijaya
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
46.76%
We consider the all pairs all shortest paths (APASP) problem, which maintains all of the multiple shortest paths for every vertex pair in a directed graph G=(V,E) with a positive real weight on each edge. We present a fully dynamic algorithm for this problem in which an update supports either weight increases or weight decreases on a subset of edges incident to a vertex. Our algorithm runs in amortized O(\vstar^2 \cdot \log^3 n) time per update, where n = |V|, and \vstar bounds the number of edges that lie on shortest paths through any single vertex. Our APASP algorithm leads to the same amortized bound for the fully dynamic computation of betweenness centrality (BC), which is a parameter widely used in the analysis of large complex networks. Our method is a generalization and a variant of the fully dynamic algorithm of Demetrescu and Italiano [DI04] for unique shortest path, and it builds on very recent work on decremental APASP [NPR14]. Our algorithm matches the fully dynamic amortized bound in [DI04] for graphs with unique shortest paths, though our method, and especially its analysis, are different.; Comment: This revision incorporates changes that improve the presentation. There is no change to the main result. An extended abstract of this paper will appear in Proc. ISAAC 2015...

Faster Shortest Paths in Dense Distance Graphs, with Applications

Mozes, Shay; Nussbaum, Yahav; Weimann, Oren
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 03/04/2014
Relevância na Pesquisa
46.73%
We show how to combine two techniques for efficiently computing shortest paths in directed planar graphs. The first is the linear-time shortest-path algorithm of Henzinger, Klein, Subramanian, and Rao [STOC'94]. The second is Fakcharoenphol and Rao's algorithm [FOCS'01] for emulating Dijkstra's algorithm on the dense distance graph (DDG). A DDG is defined for a decomposition of a planar graph $G$ into regions of at most $r$ vertices each, for some parameter $r < n$. The vertex set of the DDG is the set of $\Theta(n/\sqrt r)$ vertices of $G$ that belong to more than one region (boundary vertices). The DDG has $\Theta(n)$ arcs, such that distances in the DDG are equal to the distances in $G$. Fakcharoenphol and Rao's implementation of Dijkstra's algorithm on the DDG (nicknamed FR-Dijkstra) runs in $O(n\log(n) r^{-1/2} \log r)$ time, and is a key component in many state-of-the-art planar graph algorithms for shortest paths, minimum cuts, and maximum flows. By combining these two techniques we remove the $\log n$ dependency in the running time of the shortest-path algorithm, making it $O(n r^{-1/2} \log^2r)$. This work is part of a research agenda that aims to develop new techniques that would lead to faster, possibly linear-time, algorithms for problems such as minimum-cut...

Shortest Paths Avoiding Forbidden Subpaths

Ahmed, Mustaq; Lubiw, Anna
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
46.67%
In this paper we study a variant of the shortest path problem in graphs: given a weighted graph G and vertices s and t, and given a set X of forbidden paths in G, find a shortest s-t path P such that no path in X is a subpath of P. Path P is allowed to repeat vertices and edges. We call each path in X an exception, and our desired path a shortest exception-avoiding path. We formulate a new version of the problem where the algorithm has no a priori knowledge of X, and finds out about an exception x in X only when a path containing x fails. This situation arises in computing shortest paths in optical networks. We give an algorithm that finds a shortest exception avoiding path in time polynomial in |G| and |X|. The main idea is to run Dijkstra's algorithm incrementally after replicating vertices when an exception is discovered.; Comment: 12 pages, 2 figures. Fixed a few typos, rephrased a few sentences, and used the STACS style

Distributed Approximation Algorithms for Weighted Shortest Paths

Nanongkai, Danupon
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
46.73%
A distributed network is modeled by a graph having $n$ nodes (processors) and diameter $D$. We study the time complexity of approximating {\em weighted} (undirected) shortest paths on distributed networks with a $O(\log n)$ {\em bandwidth restriction} on edges (the standard synchronous \congest model). The question whether approximation algorithms help speed up the shortest paths (more precisely distance computation) was raised since at least 2004 by Elkin (SIGACT News 2004). The unweighted case of this problem is well-understood while its weighted counterpart is fundamental problem in the area of distributed approximation algorithms and remains widely open. We present new algorithms for computing both single-source shortest paths (\sssp) and all-pairs shortest paths (\apsp) in the weighted case. Our main result is an algorithm for \sssp. Previous results are the classic $O(n)$-time Bellman-Ford algorithm and an $\tilde O(n^{1/2+1/2k}+D)$-time $(8k\lceil \log (k+1) \rceil -1)$-approximation algorithm, for any integer $k\geq 1$, which follows from the result of Lenzen and Patt-Shamir (STOC 2013). (Note that Lenzen and Patt-Shamir in fact solve a harder problem, and we use $\tilde O(\cdot)$ to hide the $O(\poly\log n)$ term.) We present an $\tilde O(n^{1/2}D^{1/4}+D)$-time $(1+o(1))$-approximation algorithm for \sssp. This algorithm is {\em sublinear-time} as long as $D$ is sublinear...

Shortest Paths in Microseconds

Agarwal, Rachit; Caesar, Matthew; Godfrey, P. Brighten; Zhao, Ben Y.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 03/09/2013
Relevância na Pesquisa
46.76%
Computing shortest paths is a fundamental primitive for several social network applications including socially-sensitive ranking, location-aware search, social auctions and social network privacy. Since these applications compute paths in response to a user query, the goal is to minimize latency while maintaining feasible memory requirements. We present ASAP, a system that achieves this goal by exploiting the structure of social networks. ASAP preprocesses a given network to compute and store a partial shortest path tree (PSPT) for each node. The PSPTs have the property that for any two nodes, each edge along the shortest path is with high probability contained in the PSPT of at least one of the nodes. We show that the structure of social networks enable the PSPT of each node to be an extremely small fraction of the entire network; hence, PSPTs can be stored efficiently and each shortest path can be computed extremely quickly. For a real network with 5 million nodes and 69 million edges, ASAP computes a shortest path for most node pairs in less than 49 microseconds per pair. ASAP, unlike any previous technique, also computes hundreds of paths (along with corresponding distances) between any node pair in less than 100 microseconds. Finally...

Finding $k$ Simple Shortest Paths and Cycles

Agarwal, Udit; Ramachandran, Vijaya
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 07/12/2015
Relevância na Pesquisa
46.89%
The problem of finding multiple simple shortest paths in a weighted directed graph $G=(V,E)$ has many applications, and is considerably more difficult than the corresponding problem when cycles are allowed in the paths. Even for a single source-sink pair, it is known that two simple shortest paths cannot be found in time polynomially smaller than $n^3$ (where $n=|V|$) unless the All-Pairs Shortest Paths problem can be solved in a similar time bound. The latter is a well-known open problem in algorithm design. We consider the all-pairs version of the problem, and we give a new algorithm to find $k$ simple shortest paths for all pairs of vertices. For $k=2$, our algorithm runs in $O(mn + n^2 \log n)$ time (where $m=|E|$), which is almost the same bound as for the single pair case, and for $k=3$ we improve earlier bounds. Our approach is based on forming suitable path extensions to find simple shortest paths; this method is different from the `detour finding' technique used in most of the prior work on simple shortest paths, replacement paths, and distance sensitivity oracles. Enumerating simple cycles is a well-studied classical problem. We present new algorithms for generating simple cycles and simple paths in $G$ in non-decreasing order of their weights; the algorithm for generating simple paths is much faster...

Computing L1 Shortest Paths among Polygonal Obstacles in the Plane

Chen, Danny Z.; Wang, Haitao
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 25/02/2012
Relevância na Pesquisa
46.7%
Given a point $s$ and a set of $h$ pairwise disjoint polygonal obstacles of totally $n$ vertices in the plane, we present a new algorithm for building an $L_1$ shortest path map of size O(n) in $O(T)$ time and O(n) space such that for any query point $t$, the length of the $L_1$ shortest obstacle-avoiding path from $s$ to $t$ can be reported in $O(\log n)$ time and the actual shortest path can be found in additional time proportional to the number of edges of the path, where $T$ is the time for triangulating the free space. It is currently known that $T=O(n+h\log^{1+\epsilon}h)$ for an arbitrarily small constant $\epsilon>0$. If the triangulation can be done optimally (i.e., $T=O(n+h\log h)$), then our algorithm is optimal. Previously, the best algorithm computes such an $L_1$ shortest path map in $O(n\log n)$ time and O(n) space. Our techniques can be extended to obtain improved results for other related problems, e.g., computing the $L_1$ geodesic Voronoi diagram for a set of point sites in a polygonal domain, finding shortest paths with fixed orientations, finding approximate Euclidean shortest paths, etc.; Comment: 48 pages; 19 figures; partial results appeared in ESA 2011

Shortest paths between shortest paths and independent sets

Kaminski, Marcin; Medvedev, Paul; Milanic, Martin
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
46.67%
We study problems of reconfiguration of shortest paths in graphs. We prove that the shortest reconfiguration sequence can be exponential in the size of the graph and that it is NP-hard to compute the shortest reconfiguration sequence even when we know that the sequence has polynomial length. Moreover, we also study reconfiguration of independent sets in three different models and analyze relationships between these models, observing that shortest path reconfiguration is a special case of independent set reconfiguration in perfect graphs, under any of the three models. Finally, we give polynomial results for restricted classes of graphs (even-hole-free and $P_4$-free graphs).

All-Pairs Shortest Paths in $O(n^2)$ time with high probability

Peres, Yuval; Sotnikov, Dimitry; Sudakov, Benny; Zwick, Uri
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 18/05/2011
Relevância na Pesquisa
46.7%
We present an all-pairs shortest path algorithm whose running time on a complete directed graph on $n$ vertices whose edge weights are chosen independently and uniformly at random from $[0,1]$ is $O(n^2)$, in expectation and with high probability. This resolves a long standing open problem. The algorithm is a variant of the dynamic all-pairs shortest paths algorithm of Demetrescu and Italiano. The analysis relies on a proof that the number of \emph{locally shortest paths} in such randomly weighted graphs is $O(n^2)$, in expectation and with high probability. We also present a dynamic version of the algorithm that recomputes all shortest paths after a random edge update in $O(\log^{2}n)$ expected time.

Decremental All-Pairs ALL Shortest Paths and Betweenness Centrality

Nasre, Meghana; Pontecorvi, Matteo; Ramachandran, Vijaya
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 14/11/2014
Relevância na Pesquisa
46.76%
We consider the all pairs all shortest paths (APASP) problem, which maintains the shortest path dag rooted at every vertex in a directed graph G=(V,E) with positive edge weights. For this problem we present a decremental algorithm (that supports the deletion of a vertex, or weight increases on edges incident to a vertex). Our algorithm runs in amortized O(\vstar^2 \cdot \log n) time per update, where n=|V|, and \vstar bounds the number of edges that lie on shortest paths through any given vertex. Our APASP algorithm can be used for the decremental computation of betweenness centrality (BC), a graph parameter that is widely used in the analysis of large complex networks. No nontrivial decremental algorithm for either problem was known prior to our work. Our method is a generalization of the decremental algorithm of Demetrescu and Italiano [DI04] for unique shortest paths, and for graphs with \vstar =O(n), we match the bound in [DI04]. Thus for graphs with a constant number of shortest paths between any pair of vertices, our algorithm maintains APASP and BC scores in amortized time O(n^2 \log n) under decremental updates, regardless of the number of edges in the graph.; Comment: An extended abstract of this paper will appear in Proc. ISAAC 2014