More Like this

1. Finding shortest and nearly shortest path nodes in large substantially incomplete networks by hyperbolic mapping

   https://doi.org/10.1038/s41467-022-35181-w  

   Kitsak, Maksim ; Ganin, Alexander ; Elmokashfi, Ahmed ; Cui, Hongzhu ; Eisenberg, Daniel_A ; Alderson, David_L ; Korkin, Dmitry ; Linkov, Igor ( January 2023 , Nature Communications)

   Dynamic processes on networks, be it information transfer in the Internet, contagious spreading in a social network, or neural signaling, take place along shortest or nearly shortest paths. Computing shortest paths is a straightforward task when the network of interest is fully known, and there are a plethora of computational algorithms for this purpose. Unfortunately, our maps of most large networks are substantially incomplete due to either the highly dynamic nature of networks, or high cost of network measurements, or both, rendering traditional path finding methods inefficient. We find that shortest paths in large real networks, such as the network of protein-protein interactions and the Internet at the autonomous system level, are not random but are organized according to latent-geometric rules. If nodes of these networks are mapped to points in latent hyperbolic spaces, shortest paths in them align along geodesic curves connecting endpoint nodes. We find that this alignment is sufficiently strong to allow for the identification of shortest path nodes even in the case of substantially incomplete networks, where numbers of missing links exceed those of observable links. We demonstrate the utility of latent-geometric path finding in problems of cellular pathway reconstruction and communication security.

    

   more » « less
2. Turn Constrained Shortest Path

   https://doi.org/10.1109/HONET59747.2023.10374669  

   Allani, Amogh ; Yang, KwangSoo ( December 2023 , International Conference on Smart Communities: Improving Quality of Life using AI, Robotics and IoT (HONET))

   Given a transportation network, a source node s, a destination node t , and the number of maximum possible turnings b , the Turn-Constrained Shortest Path (TCSP) problem is to find the route that minimizes the travel distance and meets the turn-constraint. The TCSP problem is important for societal applications such as shipping and logistics, emergency route planning, and traffic management services. We propose novel approaches for TCSP to meet the turn-constraint while minimizing the travel distance for the vehicle route. Experiments using real-world datasets demonstrated that the proposed algorithms can minimize the travel distance and meet the turn-constraint; furthermore, it has comparable solution quality to the unconstrained shortest path and significantly reduces the computational cost. 

   more » « less
3. Shortest Program Interpolation Learning

   Manoj, Naren Sarayu ; Srebro, Nati ( January 2023 , The Thirty Sixth Annual Conference on Learning Theory)
4. Circuit Decompositions and Shortest Circuit Coverings of Hypergraphs

   https://doi.org/10.1007/s00373-018-1881-0  

   Kang, Liying ; Lu, Weihua ; Wu, Yezhou ; Ye, Dong ; Zhang, Cun-Quan ( March 2018 , Graphs and Combinatorics)
5. New Additive Approximations for Shortest Paths and Cycles

   Deng, Mingyang ; Kirkpatrick, Yael ; Rong, Victor ; Vassilevska Williams, Virginia ; Zhong, Ziqian ( January 2022 , 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022))