arXiv preprint ·
$c$-Packedness versus $λ$-Low-Density in Geometric Graphs: Theory and Practice
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
When designing algorithms for geometric graphs, exploiting structural parameters can lead to significantly improved bounds. Two prominent parameters in this context are $c$-packedness and $λ$-low density, both of which locally restrict graph complexity. Parameterized algorithms based on these parameters have been developed for computing well-separated pair decompositions, balanced separators, as well as distance oracles. Nevertheless the practical applicability of algorithms parameterized by $c$ or $λ$ remains unclear. While $c$-packed and $λ$-low-density graphs have been proposed as realistic models for road networks, the actual parameter values of large real-world instances have so far remained unknown, and existing theoretical guarantees are partially too loose for practical usage. In this paper we first devise scalable implementations for the approximate computation of $c$ and the exact computation of $λ$. Our experiments on road networks with millions of edges reveals a significant gap between the two parameters. On the theoretical side we prove that $c\in O(λ\sqrt n)$ which complements the known result that $λ\in O(c)$. Furthermore we present improved parameterized algorithms for balanced separator computation that reduce the separator size in theory and practice. We also show how to compute a tree decomposition with a width linear in the respective parameterized balanced separator size in polynomial time. This structural result yields a variety of new algorithmic consequences. Among them is an exact distance oracle with query time $O(c)$ for $c$-packed graphs after polynomial-time preprocessing, which improves upon the previous $O(c\log n)$ bound. Our experiments show that the proposed techniques efficiently produce small balanced separators and enable the construction of concise exact distance oracles on large road networks.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
WildHSR: Metric Feed-Forward 4D People-Scene Reconstruction from a 3D Foundation Model
Homological Trimming and Regularity of Filtrations via Local Obstruction Modules
Linear-Time FPT Algorithm for Surface Disjoint Paths via Surface Cutting
Approximation Algorithm for the Min-Cost Bipartite Matching with Penalties
Frame-to-Panorama Localization and Context-Aware Sampling for Scene-Specific Ship Detection in a Smart Marina Testbed
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.