Eccentricity queries and beyond using hub labels

DOI10.1016/j.tcs.2022.07.017OpenAlexW3097417538MaRDI QIDQ2166770

Guillaume Ducoffe

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

zbMATH Keywords

topological indicesdistance-sum computationeccentricity computationgraph classes of bounded expansionhub labels

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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