Optimal reachability and a space-time tradeoff for distance queries in constant-treewidth graphs

DOI10.4230/LIPICS.ESA.2016.28MaRDI QIDQ4606297zbMATH OpenOpenAlexFDO

Authors Krishnendu Chatterjee, Rasmus Ibsen-Jensen, Andreas Pavlogiannis

Publication date 2 March 2018

Full work available at URL https://dblp.uni-trier.de/db/conf/esa/esa2016.html#ChatterjeeIP16

zbMATH Keywords

graph algorithmsdistance queriesreachability queriesconstant-treewidth graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distance in graphs (05C12)

Recommendations

• Compact navigation and distance oracles for graphs with small treewidth
• Compact navigation and distance oracles for graphs with small treewidth
• Shortest path queries in digraphs of small treewidth
• Shortest paths in digraphs of small treewidth. I: Sequential algorithms
• Optimal parallel shortest paths in small treewidth digraphs

Cited in

(3)

• The PACE 2017 parameterized algorithms and computational experiments challenge: the second iteration
• Compact navigation and distance oracles for graphs with small treewidth
• Compact navigation and distance oracles for graphs with small treewidth

This page was built for publication: Optimal reachability and a space-time tradeoff for distance queries in constant-treewidth graphs

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