Cover Image

Dynamic Connectivity in Disk Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Baumann, Alexander, Kaplan, Haim, Klost, Katharina, Knorr, Kristin, Mulzer, Wolfgang, Roditty, Liam, Seiferth, Paul
Format:	Preprint
Published:	2021
Subjects:	Computational Geometry Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles I: Treewidth, Pathwidth, and Grid Graphs
by: Beisegel, Jesse, et al.
Published: (2025)

A Graph Width Perspective on Partially Ordered Hamiltonian Paths
by: Beisegel, Jesse, et al.
Published: (2025)

A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles II: Vertex and Edge Deletion Numbers
by: Beisegel, Jesse, et al.
Published: (2025)

Robust Algorithms for Finding Triangles and Computing the Girth in Unit Disk and Transmission Graphs
by: Klost, Katharina, et al.
Published: (2024)

Additive, Near-Additive, and Multiplicative Approximations for APSP in Weighted Undirected Graphs: Trade-offs and Algorithms
by: Roditty, Liam, et al.
Published: (2025)

Maximum Matchings in Geometric Intersection Graphs
by: Bonnet, Édouard, et al.
Published: (2019)

Maximum Independent Sets in Disk Graphs with Disks in Convex Position
by: Tkachenko, Anastasiia, et al.
Published: (2026)

Computing Maximum Cliques in Unit Disk Graphs
by: Tkachenko, Anastasiia, et al.
Published: (2025)

Parameterized Geometric Graph Modification with Disk Scaling
by: Fomin, Fedor V., et al.
Published: (2024)

Shortest Path Separators in Unit Disk Graphs
by: Harb, Elfarouk, et al.
Published: (2024)

Dynamic Unit-Disk Range Reporting
by: Wang, Haitao, et al.
Published: (2024)

An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs
by: Brewer, Bruce W., et al.
Published: (2025)

New approximate distance oracles and their applications
by: Kadria, Avi, et al.
Published: (2025)

Faster Algorithms for $(2k-1)$-Stretch Distance Oracles
by: Kadria, Avi, et al.
Published: (2025)

New algorithms for girth and cycle detection
by: Roditty, Liam, et al.
Published: (2025)

Single-Source Shortest Path Problem in Weighted Disk Graphs
by: An, Shinwoo, et al.
Published: (2025)

An Improved Algorithm for Shortest Paths in Weighted Unit-Disk Graphs
by: Brewer, Bruce W., et al.
Published: (2024)

Computing Dominating Sets in Disk Graphs with Centers in Convex Position
by: Tkachenko, Anastasiia, et al.
Published: (2026)

ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs
by: An, Shinwoo, et al.
Published: (2024)

Computing Diameter +1 in Truly Subquadratic Time for Unit-Disk Graphs
by: Chang, Hsien-Chih, et al.
Published: (2024)

Subexponential Algorithms for Clique Cover on Unit Disk and Unit Ball Graphs
by: Koana, Tomohiro, et al.
Published: (2024)

Bipartizing (Pseudo-)Disk Graphs: Approximation with a Ratio Better than 3
by: Lokshtanov, Daniel, et al.
Published: (2024)

Subcoloring of (Unit) Disk Graphs
by: Marin, Malory, et al.
Published: (2025)

Framework for $\exists \mathbb{R}$-Completeness of Two-Dimensional Packing Problems
by: Abrahamsen, Mikkel, et al.
Published: (2020)

Revisiting Graph Modification via Disk Scaling: From One Radius to Interval-Based Radii
by: Depian, Thomas, et al.
Published: (2026)

Weighted Emulators with Local Heaviest Edges Stretch for Undirected Graphs
by: Roditty, Liam, et al.
Published: (2026)

Caching Connections in Matchings
by: Sadeh, Yaniv, et al.
Published: (2023)

Faster Algorithms for Reverse Shortest Path in Unit-Disk Graphs and Related Geometric Optimization Problems: Improving the Shrink-and-Bifurcate Technique
by: Chan, Timothy M., et al.
Published: (2025)

On the Space Usage of Approximate Distance Oracles with Sub-2 Stretch
by: Kopelowitz, Tsvi, et al.
Published: (2023)

On the Line-Separable Unit-Disk Coverage and Related Problems
by: Liu, Gang, et al.
Published: (2023)

On Computing Vertex Connectivity of 1-Plane Graphs
by: Biedl, Therese, et al.
Published: (2022)

On Line-Separable Weighted Unit-Disk Coverage and Related Problems
by: Liu, Gang, et al.
Published: (2024)

Unweighted Geometric Hitting Set for Line-Constrained Disks and Related Problems
by: Liu, Gang, et al.
Published: (2024)

Morphing Planar Graph Drawings Through 3D
by: Buchin, Kevin, et al.
Published: (2022)

Structure and Independence in Hyperbolic Uniform Disk Graphs
by: Bläsius, Thomas, et al.
Published: (2024)

Beyond Vizing Chains: Improved Recourse in Dynamic Edge Coloring
by: Sadeh, Yaniv, et al.
Published: (2026)

Better Diameter Algorithms for Bounded VC-dimension Graphs and Geometric Intersection Graphs
by: Duraj, Lech, et al.
Published: (2023)

Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs
by: de Berg, Mark, et al.
Published: (2026)

New Diameter Approximations via Distance Oracle Techniques
by: Kirkpatrick, Yael, et al.
Published: (2026)

Unit-length Rectangular Drawings of Graphs
by: Alegria, Carlos, et al.
Published: (2022)