Compact Navigation and Distance Oracles for Graphs with Small Treewidth

DOI10.1007/978-3-642-22006-7_23zbMath1332.68170MaRDI QIDQ3012812

Shahin Kamali, Arash Farzan

Publication date: 6 July 2011

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22006-7_23

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

68P05: Data structures

Related Items

A uniform paradigm to succinctly encode various families of trees, On Advice Complexity of the k-server Problem under Sparse Metrics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph treewidth and geometric thickness parameters
• On Compact Representations of All-Pairs-Shortest-Path-Distance Matrices
• Treewidth: Characterizations, Applications, and Computations
• Shorter Implicit Representation for Planar Graphs and Bounded Treewidth Graphs
• Succinct Representations of Arbitrary Graphs
• Succinct Representations of Separable Graphs
• All-pairs shortest paths for unweighted undirected graphs in o(mn) time
• Succinct indexable dictionaries with applications to encoding k -ary trees, prefix sums and multisets
• Succinct Representation of Labeled Graphs
• Succinct Ordinal Trees Based on Tree Covering