Compact navigation and distance oracles for graphs with small treewidth
From MaRDI portal
Publication:472468
DOI10.1007/s00453-012-9712-9zbMath1303.05188OpenAlexW1988115395MaRDI QIDQ472468
Publication date: 19 November 2014
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-012-9712-9
Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (9)
Succinct data structures for series-parallel, block-cactus and 3-leaf power graphs ⋮ Succinct encodings for families of interval graphs ⋮ Compact representation of graphs with bounded bandwidth or treedepth ⋮ Succinct data structure for path graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Compact representation of graphs of small clique-width ⋮ Succinct navigational oracles for families of intersection graphs on a circle ⋮ Succinct representation for (non)deterministic finite automata
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Ultra-succinct representation of ordered trees with applications
- On the succinct representation of graphs
- Succinct representations of planar maps
- On compact representations of all-pairs-shortest-path-distance matrices
- All structured programs have small tree width and good register allocation
- Surpassing the information theoretic bound with fusion trees
- On treewidth approximations.
- Short encodings of planar graphs and maps
- Graph treewidth and geometric thickness parameters
- Succinct representation of labeled graphs
- Enumeration and limit laws for series-parallel graphs
- The number of trees
- Succinct Representation of Balanced Parentheses and Static Trees
- Exploiting Bounded Signal Flow for Graph Orientation Based on Cause–Effect Pairs
- A Uniform Approach Towards Succinct Representation of Trees
- Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
- Treewidth: Characterizations, Applications, and Computations
- Shorter Implicit Representation for Planar Graphs and Bounded Treewidth Graphs
- Succinct Representations of Arbitrary Graphs
- Approximate distance oracles
- Succinct Representations of Separable Graphs
- All-pairs shortest paths for unweighted undirected graphs in o(mn) time
- Universal Succinct Representations of Trees?
- Implicat Representation of Graphs
- Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
- Succinct indexable dictionaries with applications to encoding k -ary trees, prefix sums and multisets
- Two strikes against perfect phylogeny
- Algorithms and Data Structures
- Succinct Ordinal Trees Based on Tree Covering
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Asymmetric graphs
This page was built for publication: Compact navigation and distance oracles for graphs with small treewidth
