Disk-based shortest path discovery using distance index over large dynamic graphs

DOI10.1016/J.INS.2016.12.013MaRDI QIDQ2292955zbMATH OpenOpenAlexFDO

Authors Jihye Hong, Kisung Park, Yongkoo Han, Mostofa Kamal Rasel, Dawanga Vonvou, Young-Koo Lee

Publication date 6 February 2020

Published in Information Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ins.2016.12.013

zbMATH Keywords

dynamic graphsgraph searchinglarge graphsshortest path discovery

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Shortest paths on dynamic graphs
• Shortest-path algorithms and dynamic cost changes
• An all pairs shortest path algorithm for dynamic graphs
• Efficient single-pair all-shortest-path query processing for massive dynamic networks
• A single-source shortest path algorithm for dynamic graphs

Cites work

• A new approach to dynamic all pairs shortest paths
• A note on two problems in connexion with graphs
• Collective dynamics of `small-world' networks
• Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters
• Compact roundtrip routing in directed networks
• Computing the shortest path: A^ search meets graph theory
• Faster shortest-path algorithms for planar graphs
• scientific article; zbMATH DE number 3900809 (Why is no real title available?)
• scientific article; zbMATH DE number 3907787 (Why is no real title available?)
• Incremental algorithms for minimal length paths
• Speed-Up Techniques for Shortest-Path Computations
• The structure of scientific collaboration networks

Describes a project that uses

Uses Software

• GraphLab
• Pregel
• PowerGraph
• MapReduce
• gSpan

This page was built for publication: Disk-based shortest path discovery using distance index over large dynamic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2292955)