Tree decomposition-based indexing for efficient shortest path and nearest neighbors query answering on graphs

DOI10.1016/j.jcss.2015.06.008zbMath1343.68072OpenAlexW910816382MaRDI QIDQ891679

Fang Wei-Kleiner

Publication date: 17 November 2015

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2015.06.008

zbMATH Keywords

shortest pathtree decompositiongraph indexing\(k\)-nearest neighbors problemsgraphs algorithms

Mathematics Subject Classification ID

Database theory (68P15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

Foreword: Journal of Computer and System Sciences special issue on query answering on graph-structured data ⋮ Space efficient algorithm for solving reachability using tree decomposition and separators

Uses Software

• Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• Graph minors. III. Planar tree-width
• Unifying tree decompositions for reasoning in graphical models
• Shortest Path Algorithms: An Evaluation Using Real Road Networks
• Emergence of Scaling in Random Networks
• Complexity of Finding Embeddings in a k-Tree
• Planar graph decomposition and all pairs shortest paths
• Reachability and Distance Queries via 2-Hop Labels
• Shortest-path queries in static networks
• Point-to-Point Shortest Path Algorithms with Preprocessing

This page was built for publication: Tree decomposition-based indexing for efficient shortest path and nearest neighbors query answering on graphs