Computing All-Pairs Shortest Paths by Leveraging Low Treewidth

Léon Planken, Mathijs de Weerdt, Roman van der Krogt

JAIR 2012 pp. 353-388

doi:10.1613/JAIR.3509 /jair/2012/planken2012jair-computing/

Abstract

We present two new and efficient algorithms for computing all-pairs shortest paths. The algorithms operate on directed graphs with real (possibly negative) weights. They make use of directed path consistency along a vertex ordering d. Both algorithms run in O(n^2 w_d) time, where w_d is the graph width induced by this vertex ordering. For graphs of constant treewidth, this yields O(n^2) time, which is optimal. On chordal graphs, the algorithms run in O(nm) time. In addition, we present a variant that exploits graph separators to arrive at a run time of O(n w_d^2 + n^2 s_d) on general graphs, where s_d

PDF JAIR Semantic Scholar

Cite

Text

Planken et al. "Computing All-Pairs Shortest Paths by Leveraging Low Treewidth." Journal of Artificial Intelligence Research, 2012. doi:10.1613/JAIR.3509

Markdown

[Planken et al. "Computing All-Pairs Shortest Paths by Leveraging Low Treewidth." Journal of Artificial Intelligence Research, 2012.](https://mlanthology.org/jair/2012/planken2012jair-computing/) doi:10.1613/JAIR.3509

BibTeX

@article{planken2012jair-computing,
  title     = {{Computing All-Pairs Shortest Paths by Leveraging Low Treewidth}},
  author    = {Planken, Léon and de Weerdt, Mathijs and van der Krogt, Roman},
  journal   = {Journal of Artificial Intelligence Research},
  year      = {2012},
  pages     = {353-388},
  doi       = {10.1613/JAIR.3509},
  volume    = {43},
  url       = {https://mlanthology.org/jair/2012/planken2012jair-computing/}
}