Shortest beer path queries based on graph decomposition

DOI10.4230/LIPICS.ISAAC.2023.37MaRDI QIDQ6953182zbMATH OpenFDO

Authors Tesshu Hanaka, Hirotaka Ono, Kunihiko Sadakane, Kosuke Sugiyama

Publication date 24 July 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ISAAC.2023.37

zbMATH Keywords

graph algorithmshortest path problemSPQR tree

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• Compact navigation and distance oracles for graphs with small treewidth
• Computing on a free tree via complexity-preserving mappings
• Dividing a Graph into Triconnected Components
• Faster algorithms for shortest path and network flow based on graph decomposition
• Fibonacci heaps and their uses in improved network optimization algorithms
• scientific article; zbMATH DE number 2080088 (Why is no real title available?)
• scientific article; zbMATH DE number 1361465 (Why is no real title available?)
• Recursive Star-Tree Parallel Data Structure
• Shortest beer path queries in interval graphs
• Shortest beer path queries in outerplanar graphs
• Undirected single-source shortest paths with positive integer weights in linear time

Cited in

(3)

• The maximum beer flow problem
• Shortest beer path queries in digraphs with bounded treewidth
• Graph spanners for group Steiner distances

This page was built for publication: Shortest beer path queries based on graph decomposition

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