Eccentricity queries and beyond using hub labels
From MaRDI portal
Publication:2166770
DOI10.1016/j.tcs.2022.07.017OpenAlexW3097417538MaRDI QIDQ2166770
Publication date: 25 August 2022
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2010.15794
topological indicesdistance-sum computationeccentricity computationgraph classes of bounded expansionhub labels
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On computing the diameter of real-world undirected graphs
- Sparsity. Graphs, structures, and algorithms
- Into the square: on the complexity of some quadratic-time solvable problems
- Algorithms for graphs of bounded treewidth via orthogonal range searching
- On the all-pairs-shortest-path problem in unweighted undirected graphs.
- All structured programs have small tree width and good register allocation
- Computing the eccentricity distribution of large graphs
- Directed tree-width
- Fast diameter computation within split graphs
- Structural sparsity of complex networks: bounded expansion in random models and real-world graphs
- Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- A $c^k n$ 5-Approximation Algorithm for Treewidth
- Hierarchical Hub Labelings for Shortest Paths
- On the Complexity of Hub Labeling (Extended Abstract)
- Highway Dimension and Provably Efficient Shortest Path Algorithms
- On the Power of Tree-Depth for Fully Polynomial FPT Algorithms
- Batched Point Location in SINR Diagrams via Algebraic Tools
- Reachability and Distance Queries via 2-Hop Labels
- Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs
- Distance labeling in graphs
- Roundtrip spanners and roundtrip routing in directed graphs
- Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs
- Hardness of Exact Distance Queries in Sparse Graphs Through Hub Labeling
- Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension
- A Faster Parameterized Algorithm for Treedepth
- Collective dynamics of ‘small-world’ networks
- Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter
- Fast approximation algorithms for the diameter and radius of sparse graphs
- Computing the Inverse Geodesic Length in Planar Graphs and Graphs of Bounded Treewidth
This page was built for publication: Eccentricity queries and beyond using hub labels