Optimal Reachability and a Space-Time Tradeoff for Distance Queries in Constant-Treewidth Graphs

DOI10.4230/LIPIcs.ESA.2016.28zbMath1397.68030OpenAlexW2528431921MaRDI QIDQ4606297

Rasmus Ibsen-Jensen, Krishnendu Chatterjee, 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

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

Related Items (1)

Unnamed Item

This page was built for publication: Optimal Reachability and a Space-Time Tradeoff for Distance Queries in Constant-Treewidth Graphs