Effect of shortest path multiplicity on congestion of multiplex networks
New Journal of Physics, 2019 Shortest paths are representative of discrete geodesic distances in graphs, and many descriptors of networks depend on their counting. In multiplex networks, this counting is radically important to quantify the switch between layers and it has crucial ...
Albert Solé-Ribalta +2 more
doaj +1 more source
Discriminative Distance-Based Network Indices with Application to Link Prediction [PDF]
, 2018 In large networks, using the length of shortest paths as the distance measure has shortcomings. A well-studied shortcoming is that extending it to disconnected graphs and directed graphs is controversial.
Abdessalem, Talel +2 more
core +1 more source
A Unifying Formalism for Shortest Path Problems with Expensive Edge Evaluations via Lazy Best-First Search over Paths with Edge Selectors [PDF]
International Conference on Automated Planning and Scheduling, 2016 While the shortest path problem has myriad applications, the computational efficiency of suitable algorithms depends intimately on the underlying problem domain.
Christopher M. Dellin, S. Srinivasa
semanticscholar +1 more source
Distributed approximation algorithms for weighted shortest paths [PDF]
Symposium on the Theory of Computing, 2014 A distributed network is modeled by a graph having n nodes (processors) and diameter D. We study the time complexity of approximating weighted (undirected) shortest paths on distributed networks with a O (log n) bandwidth restriction on edges (the ...
Danupon Nanongkai
semanticscholar +1 more source
Associative Parallel Algorithm for Dynamic Update of the Shortest Paths Tree
Моделирование и анализ информационных систем, 2013 The paper proposes an efficient associative algorithm for dynamic update of the shortest paths tree of a directed weighted graph after deleting an edge.
A. S. Nepomniaschaya
doaj +3 more sources
Computational Geometry Column 35 [PDF]
, 1998 The subquadratic algorithm of Kapoor for finding shortest paths on a polyhedron is ...
O'Rourke, Joseph
core +5 more sources
A genetic algorithm for finding the k shortest paths in a network
Egyptian Informatics Journal, 2010 Most of the multimedia applications require the k shortest paths during the communication between a single source and multiple destinations. This problem is known as multimedia multicast routing and has been proved to be NP-complete. The paper proposes a
Ahmed Younes Hamed
doaj +1 more source
Speeding up shortest path algorithms
, 2012 Given an arbitrary, non-negatively weighted, directed graph $G=(V,E)$ we present an algorithm that computes all pairs shortest paths in time $\mathcal{O}(m^* n + m \lg n + nT_\psi(m^*, n))$, where $m^*$ is the number of different edges contained in ...
A.V. Goldberg +10 more
core +1 more source
Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs [PDF]
, 2019 We give new partially-dynamic algorithms for the all-pairs shortest paths problem in weighted directed graphs. Most importantly, we give a new deterministic incremental algorithm for the problem that handles updates in O~(mn^(4/3) log{W}/epsilon) total ...
Karczmarz, Adam, Lacki, Jakub
core +2 more sources
A Constrained Time-Dependent K Shortest Paths Algorithm Addressing Overlap and Travel Time Deviation
International Journal of Transportation Science and Technology, 2015 Theoretical research often assumes all users are homogeneous in their route choice decision and will always pick the route with the shortest travel cost, which is not necessarily the case in reality. This paper documents the research effort in developing
Xianbiao Hu, PhD, Yi-Chang Chiu
doaj +1 more source