Article
Mathematics
Iztok Peterin, Gabriel Semanisin
Summary: The shortest path cover problem examines the set of maximal shortest paths in a graph G, and how to minimize the number of points in this set to cover all maximal shortest paths. By establishing the relationship between the maximal shortest paths cover number xi(G) and other graph parameters, a linear time algorithm is proposed to calculate the exact value of the maximal shortest paths cover number xi(T) for a tree T.
Article
Computer Science, Hardware & Architecture
Tianyu Zhao, Shuai Huang, Yong Wang, Chengliang Chai, Guoliang Li
Summary: This paper proposes a learning-based method RNE and RNE+ for computing the shortest paths between two vertices on road networks, with features of fast speed, high efficiency, and low error rate, which significantly outperform existing methods in experiments.
Article
Computer Science, Hardware & Architecture
Haitao Wang
Summary: Given a set of pairwise disjoint polygonal obstacles, the problem of finding a obstacle-avoiding Euclidean shortest path between two points has been extensively studied. Previous algorithms achieved O(n log n) time and space complexity, while recent modifications reduced the space complexity to O(n). In this article, the authors propose a new algorithm with O(n + h log h) time complexity and O(n) space complexity, assuming a triangulation of the free space is provided. The algorithm outperforms previous work for relatively small numbers of obstacles and allows for efficient computation of shortest path lengths and paths.
JOURNAL OF THE ACM
(2023)
Article
Physics, Fluids & Plasmas
Ricardo Gutierrez, Carlos Perez-Espigares
Summary: The article discusses the problems of finding shortest or optimal paths in networks and optimizing weighted networks, introducing an auxiliary stochastic process of generalized Doob transform, which can be solved through the analysis of large-deviation functions.
Article
Computer Science, Artificial Intelligence
Tomas Kulvicius, Sebastian Herzog, Minija Tamosiunaite, Florentin Worgoetter
Summary: The article introduces a novel configuration of multilayer networks for solving path planning on a maze with multiple start and endpoint efficiently without the need for network training. This approach can quickly solve very large mazes with dense obstacle configurations and thousands of importance-weighted path endpoints in a single pass on parallel hardware, providing solutions identical to classical algorithms.
IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS
(2022)
Article
Environmental Studies
Mengying Cui, David Levinson
Summary: This study examines path flows for road networks by considering various cost factors and finding the route with the minimum cumulative cost. The research explores how different cost factors contribute to explaining observed link traffic flows. The results suggest that flows from various path types associated with different internal cost components, along with distance, provide the best fit for traffic flows in the Minneapolis - St. Paul metropolitan area.
ENVIRONMENT AND PLANNING B-URBAN ANALYTICS AND CITY SCIENCE
(2021)
Article
Management
Alberto Vera, Siddhartha Banerjee, Samitha Samaranayake
Summary: Motivated by the needs of modern transportation service platforms, this study addresses the problem of computing constrained shortest paths at scale using preprocessing techniques. It proposes a scalable algorithm for CSP queries and establishes the relationship between constrained highway dimension and performance. Practical algorithms are developed with additional network clustering heuristics, achieving significant speed improvements compared to existing approaches.
OPERATIONS RESEARCH
(2022)
Article
Computer Science, Hardware & Architecture
James B. Orlin, Laszlo Vegh
Summary: We propose an O(nm) algorithm for computing all-pairs shortest paths in directed graphs with nonnegative integer arc costs. This algorithm matches the complexity bound achieved by Thorup's algorithm for the same problem in undirected graphs. The key observation is that directed shortest paths problems with approximately balanced cost functions can be solved similarly to the undirected case. The algorithm first finds an approximately balanced reduced cost function in an O(m root n logn) preprocessing step, and then uses this reduced cost to solve each shortest path query in O(m) time using an adaptation of Thorup's component hierarchy method. The balancing result can also be applied to the l(infinity)-matrix balancing problem.
JOURNAL OF THE ACM
(2023)
Article
Chemistry, Multidisciplinary
Jianshi Li, Jingtao Lou, Yongle Li, Shiju Pan, Youchun Xu
Summary: This paper proposes a clothoid-curve-based trajectory tracking control method to solve tracking errors caused by the discontinuous curvature of the control curve calculated by the pure pursuit tracking algorithm. The motion model based on the Ackerman steering model is constructed for vehicle trajectory tracking. The clothoid control curves are calculated and verified by the vehicle motion and safety constraints to obtain the optimal clothoid control curve, which greatly improves the tracking accuracy compared with the pure pursuit method.
APPLIED SCIENCES-BASEL
(2023)
Article
Computer Science, Artificial Intelligence
Prosenjit Bose, Guillermo Esteban, David Orden, Rodrigo I. Silveira
Summary: We study the quality of weighted shortest paths in a discretized 2-dimensional space using a weighted triangular tessellation. We evaluate the tessellation's approximation of the space by studying three types of shortest paths: weighted shortest path, weighted shortest vertex path, and weighted shortest grid path. We provide estimates on the quality of the approximation and prove that our worst-case bounds are independent of any weight assignment.
ARTIFICIAL INTELLIGENCE
(2023)
Article
Mathematics, Applied
Alexis Goujon, Shayan Aziznejad, Alireza Naderi, Michael Unser
Summary: Generalized sampling involves the recovery of a function from response samples of linear shift-invariant systems, where the reconstructed function belongs to an integer shift-invariant space that can reproduce polynomials up to a given degree M. While it has high approximation power, there is a tradeoff on the length of the support of basis functions. The concept of the shortest-support basis aims to minimize computational costs and generates a Riesz basis.
JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS
(2021)
Article
Computer Science, Interdisciplinary Applications
Raffaele Cerulli, Francesca Guerriero, Edoardo Scalzo, Carmine Sorgente
Summary: This paper introduces a NP-hard variant of the shortest path problem, which involves exclusive-disjunction arc pairs conflicts. In this framework, a penalty has to be paid if a conflict is violated by selecting both arcs in a pair or none of them. The goal is to minimize the overall cost, defined as the sum of the costs of the traversed arcs and the penalties of the violated conflicts, by finding a path. The variant is used to model web applications test planning scenarios. The paper provides a proof of NP-hardness and proposes two mathematical programming formulations for the problem.
COMPUTERS & OPERATIONS RESEARCH
(2023)
Article
Computer Science, Information Systems
Lingxiao Li, Muhammad Aamir Cheema, Mohammed Eunus Ali, Hua Lu, Huan Li
Summary: This study focuses on the problem of alternative pathfinding in game maps. Firstly, we adapt existing techniques for road networks to find alternative paths in game maps. Then, we propose novel data structures and develop an efficient algorithm to compute high-quality alternative paths. Experimental results demonstrate that our algorithm is more than an order of magnitude faster than existing approaches and returns alternative paths of comparable quality.
WORLD WIDE WEB-INTERNET AND WEB INFORMATION SYSTEMS
(2023)
Article
Computer Science, Hardware & Architecture
Michal Dory, Merav Parter
Summary: We present improved deterministic algorithms for approximating shortest paths in the Congested Clique model of distributed computing. Our algorithms achieve polynomial time complexity and exponentially improve the previous bounds for multi-source shortest paths, all pairs shortest paths, and approximate shortest paths problems. Our approach distinguishes between short and long distances and provides separate solutions for each category. Additionally, our solutions are based on a derandomization scheme of a novel variant of the hitting set problem.
JOURNAL OF THE ACM
(2022)
Article
Computer Science, Interdisciplinary Applications
Anil Maheshwari, Arash Nouri, Jorg-Rudiger Sack
Summary: This study presents an optimal algorithm for determining the time-minimal rectilinear path among transient rectilinear obstacles. The algorithm is based on the continuous Dijkstra paradigm and is able to simulate the wavefront propagation to solve the obstacle avoidance problem. Additionally, an algorithm for computing the Euclidean shortest path map among transient polygonal obstacles is proposed, reducing the time complexity significantly.
JOURNAL OF COMBINATORIAL OPTIMIZATION
(2022)
