2022/04/23 by Domagoj Vrgoč, Vrgoč, Domagoj
Computer Science · #Algorithms and Data Compression #Data Management and Algorithms #Databases (cs.DB) #FOS: Computer and information sciences #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2204.11137
openalex publication_date 2022/04/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The purpose of this report is to explain how the textbook breadth-first search algorithm (BFS) can be modified in order to also create a compact representation of all shortest paths connecting a single source node to all the nodes reachable from it. From this representation, all these paths can also be efficiently enumerated. We then apply this algorithm to solve a similar problem in edge labelled graphs, where paths also have an additional restriction that their edge labels form a word belonging to a regular language. Namely, we solve the problem of evaluating regular path queries (RPQs) under the all-shortest paths semantics.