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

## Ranking multiobjective shortest paths

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%

#Multiple objective programming#Combinatorial optimization#Ranking algorithm#Total order#Non-dominated path

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.

Link permanente para citações:

## K-menores caminhos; k-shortest paths

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.

Link permanente para citações:

## Shortest Paths, Network Design and Associated Polyhedra

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.

Link permanente para citações:

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

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

Link permanente para citações:

## Two betweenness centrality measures based on Randomized Shortest Paths

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 10/09/2015

Relevância na Pesquisa

46.78%

#Computer Science - Social and Information Networks#Computer Science - Data Structures and Algorithms#Physics - Physics and Society

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.

Link permanente para citações:

## Combining the Shortest Paths and the Bottleneck Paths Problems

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

Link permanente para citações:

## Combining All Pairs Shortest Paths and All Pairs Bottleneck Paths Problems

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.

Link permanente para citações:

## Computing shortest paths in 2D and 3D memristive networks

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.

Link permanente para citações:

## Maximum st-flow in directed planar graphs via shortest paths

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 24/05/2013

Relevância na Pesquisa

46.65%

#Computer Science - Data Structures and Algorithms#Computer Science - Discrete Mathematics#Mathematics - Combinatorics

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

Link permanente para citações:

## Shortest Paths in Less Than a Millisecond

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 06/06/2012

Relevância na Pesquisa

46.64%

#Computer Science - Social and Information Networks#Computer Science - Databases#Physics - Physics and Society

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

Link permanente para citações:

## Fully Dynamic All Pairs All Shortest Paths

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...

Link permanente para citações:

## Faster Shortest Paths in Dense Distance Graphs, with Applications

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...

Link permanente para citações:

## Shortest Paths Avoiding Forbidden Subpaths

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Relevância na Pesquisa

46.67%

#Computer Science - Discrete Mathematics#Computer Science - Data Structures and Algorithms#G.2.2#F.2.2

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

Link permanente para citações:

## Distributed Approximation Algorithms for Weighted Shortest Paths

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...

Link permanente para citações:

## Shortest Paths in Microseconds

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 03/09/2013

Relevância na Pesquisa

46.76%

#Computer Science - Distributed, Parallel, and Cluster Computing#Computer Science - Data Structures and Algorithms#Computer Science - Social and Information Networks#Physics - Physics and Society

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...

Link permanente para citações:

## Finding $k$ Simple Shortest Paths and Cycles

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...

Link permanente para citações:

## Computing L1 Shortest Paths among Polygonal Obstacles in the Plane

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

Link permanente para citações:

## Shortest paths between shortest paths and independent sets

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).

Link permanente para citações:

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

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 18/05/2011

Relevância na Pesquisa

46.7%

#Mathematics - Combinatorics#Computer Science - Data Structures and Algorithms#Mathematics - Probability

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.

Link permanente para citações:

## Decremental All-Pairs ALL Shortest Paths and Betweenness Centrality

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

Link permanente para citações: