Results 31 to 40 of about 190,109 (292)
SIAM Journal on Computing, 1998 Summary: We give algorithms for finding the \(k\) shortest paths (not required to be simple) connecting a pair of vertices in a digraph. Our algorithms output an implicit representation of these paths in a digraph with \(n\) vertices and \(m\) edges, in time \(O(m+n\log n+k)\). We can also find the \(k\) shortest paths from a given source \(s\) to each
openaire +2 more sources
Log-space Algorithms for Paths and Matchings in k-trees [PDF]
, 2010 Reachability and shortest path problems are NL-complete for general graphs. They are known to be in L for graphs of tree-width 2 [JT07]. However, for graphs of tree-width larger than 2, no bound better than NL is known.
Das, Bireswar +2 more
core +3 more sources
K-shortest simple paths using biobjective path search
Mathematical Programming ComputationIn this paper we introduce a new algorithm for the \emph{$k$-Shortest Simple Paths} (\kspp{k}) problem with an asymptotic running time matching the state of the art from the literature. It is based on a black-box algorithm due to \citet{Roditty12} that solves at most $2k$ instances of the \emph{Second Shortest Simple Path} (\kspp{2}) problem without ...
Maristany de las Casas, Pedro +3 more
openaire +2 more sources
KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation [PDF]
, 2016 We present KADABRA, a new algorithm to approximate betweenness centrality in directed and undirected graphs, which significantly outperforms all previous approaches on real-world complex networks.
Borassi, Michele, Natale, Emanuele
core +3 more sources
A new algorithm for finding the K shortest paths in a time-schedule network with constraints on arcs
Journal of Algorithms & Computational Technology, 2017 Time-schedule network with constraints on arcs (TSNCA) means network with a list of pre-defined departure times for each arc. Compared to past research on finding the K shortest paths in TSNCA, the algorithm in this paper is suitable for networks having ...
Jianyuan Guo, Limin Jia
doaj +1 more source
Multiattribute Evaluation Model Based on the KSP Algorithm for Edge Computing
IEEE Access, 2020 To solve the problems of single evaluation attributes and highly overlapping trust paths in the current trust model, a multiattribute trust evaluation model based on the K shortest paths (KSP) algorithm is proposed.
Ruizhong Du, Kunqi Xu, Xiaoyan Liang
doaj +1 more source
Degree-dependent intervertex separation in complex networks [PDF]
, 2006 We study the mean length $\ell(k)$ of the shortest paths between a vertex of degree $k$ and other vertices in growing networks, where correlations are essential.
Dorogovtsev, S. N. +2 more
core +2 more sources
Energy Reports, 2022 Most system restoration strategies following blackouts are obtained by offline methods, which are efficient in theory. But this may not be the case. A new method is proposed to decide the generator startup sequence during the system restoration.
Zirui Wu +3 more
doaj +1 more source
Efficiently computing Top-K shortest path join [PDF]
, 2015 © 2015, Copyright is with the authors. Driven by many applications, in this paper we study the problem of computing the top-k shortest paths from one set of target nodes to another set of target nodes in a graph, namely the top-k shortest path join (KPJ)
Chang, L, Lin, X, Pei, J, Qin, L, Yu, JX
core +1 more source
A Sidetrack-Based Algorithm for Finding the k Shortest Simple Paths in a Directed Graph [PDF]
, 2016 We present an algorithm for the k shortest simple path problem on weighted directed graphs (kSSP) that is based on Eppstein's algorithm for a similar problem in which paths are allowed to contain cycles.
Kurz, Denis, Mutzel, Petra
core +2 more sources