2016/03/30 by Brandon Smock, Smock, Brandon, Joseph N. Wilson +1
Computer Science · Engineering · #68R10 #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #G.2.2 #G.2.3 #Transportation Safety and Impact Analysis #Vehicular Ad Hoc Networks (VANETs)
paper · pdf · doi:10.48550/arxiv.1603.09205
openalex publication_date 2016/03/30 · openalex created_date 2022/08/28 · openalex updated_date 2026/07/28
In this paper, we consolidate and expand upon the current theory and\npotential applications of the set of k best \cascading via-paths (CVPs)\nand the \reciprocal pointer chain (RPC) method for identifying them. CVPs\nare a collection of up to |V| paths between a source and a target node in a\ngraph G = (V,E), computed using two shortest path trees, that have\ndistinctive properties relative to other path sets. They have been shown to be\nparticularly useful in geospatial applications, where they are an intuitive and\nefficient means for identifying a set of spatially diverse alternatives to the\nsingle shortest path between the source and target. However, spatial diversity\nis not intrinsic to paths in a graph, and little theory has been developed\noutside of application to describe the nature of these paths and the RPC method\nin general. Here we divorce the RPC method from its typical geospatial\napplications and develop a comprehensive theory of CVPs from an abstract\ngraph-theoretic perspective. Restricting ourselves to properties of the CVPs\nand of the entire set of k-best CVPs that can be computed in O(|E| + |V|\n\log |V|), we are able to then propose, among other things, new and efficient\napproaches to problems such as generating a diverse set of paths and to\ncomputing the k shortest loopless paths between two nodes in a graph. We\nconclude by demonstrating the new theory in practice, first for a typical\napplication of finding alternative routes in road networks and then for a novel\napplication of identifying layer-boundaries in ground-penetrating radar (GPR)\ndata. It is our hope that by generalizing the RPC method, providing a sound\ntheoretical foundation, and demonstrating novel uses, we are able to broaden\nits perceived applicability and stimulate new research in this area, both\napplied and theoretical.\n