Buchumschlag

Shortest Path Separators in Unit Disk Graphs

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Harb, Elfarouk, Huang, Zhengcheng, Zheng, Da Wei
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Computational Geometry Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

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

An Improved Algorithm for Shortest Paths in Weighted Unit-Disk Graphs
von: Brewer, Bruce W., et al.
Veröffentlicht: (2024)

An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs
von: Brewer, Bruce W., et al.
Veröffentlicht: (2025)

Single-Source Shortest Path Problem in Weighted Disk Graphs
von: An, Shinwoo, et al.
Veröffentlicht: (2025)

New Prophet Inequalities via Poissonization and Sharding
von: Harb, Elfarouk
Veröffentlicht: (2023)

On the Line-Separable Unit-Disk Coverage and Related Problems
von: Liu, Gang, et al.
Veröffentlicht: (2023)

On Line-Separable Weighted Unit-Disk Coverage and Related Problems
von: Liu, Gang, et al.
Veröffentlicht: (2024)

Computing Maximum Cliques in Unit Disk Graphs
von: Tkachenko, Anastasiia, et al.
Veröffentlicht: (2025)

Subexponential Algorithms for Clique Cover on Unit Disk and Unit Ball Graphs
von: Koana, Tomohiro, et al.
Veröffentlicht: (2024)

Shortest Paths on Convex Polyhedral Surfaces
von: Wang, Haitao
Veröffentlicht: (2025)

Subcoloring of (Unit) Disk Graphs
von: Marin, Malory, et al.
Veröffentlicht: (2025)

ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs
von: An, Shinwoo, et al.
Veröffentlicht: (2024)

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

Dynamic Unit-Disk Range Reporting
von: Wang, Haitao, et al.
Veröffentlicht: (2024)

Unit-length Rectangular Drawings of Graphs
von: Alegria, Carlos, et al.
Veröffentlicht: (2022)

Faster Goal-Oriented Shortest Path Search for Bulk and Incremental Detailed Routing
von: Ahrens, Markus, et al.
Veröffentlicht: (2021)

Towards Space Efficient Two-Point Shortest Path Queries in a Polygonal Domain
von: de Berg, Sarita, et al.
Veröffentlicht: (2023)

Maximum Independent Sets in Disk Graphs with Disks in Convex Position
von: Tkachenko, Anastasiia, et al.
Veröffentlicht: (2026)

Dynamic Connectivity in Disk Graphs
von: Baumann, Alexander, et al.
Veröffentlicht: (2021)

Single-Source Shortest Paths and Almost Exact Diameter in Pseudodisk Graphs
von: de Berg, Mark, et al.
Veröffentlicht: (2026)

Parameterized Geometric Graph Modification with Disk Scaling
von: Fomin, Fedor V., et al.
Veröffentlicht: (2024)

Computing Dominating Sets in Disk Graphs with Centers in Convex Position
von: Tkachenko, Anastasiia, et al.
Veröffentlicht: (2026)

Bipartizing (Pseudo-)Disk Graphs: Approximation with a Ratio Better than 3
von: Lokshtanov, Daniel, et al.
Veröffentlicht: (2024)

Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs
von: de Berg, Mark, et al.
Veröffentlicht: (2026)

Charting the Diameter Computation Landscape of Geometric Intersection Graphs in Three Dimensions and Higher
von: Chan, Timothy M., et al.
Veröffentlicht: (2026)

Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension
von: Chan, Timothy M., et al.
Veröffentlicht: (2025)

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

Robust Algorithms for Path and Cycle Problems in Geometric Intersection Graphs
von: Marin, Malory, et al.
Veröffentlicht: (2025)

Corporate Needs You to Find the Difference: Revisiting Submodular and Supermodular Ratio Optimization Problems
von: Harb, Elfarouk, et al.
Veröffentlicht: (2025)

Small Independent Sets versus Small Separator in Geometric Intersection Graphs
von: Marin, Malory, et al.
Veröffentlicht: (2026)

Counting Unit Circular Arc Intersections
von: Wang, Haitao
Veröffentlicht: (2026)

Shortest Paths in Multimode Graphs
von: Kirkpatrick, Yael, et al.
Veröffentlicht: (2025)

Unweighted Geometric Hitting Set for Line-Constrained Disks and Related Problems
von: Liu, Gang, et al.
Veröffentlicht: (2024)

Unfairly Splitting Separable Necklaces
von: Schnider, Patrick, et al.
Veröffentlicht: (2024)

Dynamic Convex Hulls for Simple Paths
von: Brewer, Bruce, et al.
Veröffentlicht: (2024)

Uncrossed Multiflows and Applications to Disjoint Paths
von: Chekuri, Chandra, et al.
Veröffentlicht: (2025)

Continuous Map Matching to Paths under Travel Time Constraints
von: Bosch, Yannick, et al.
Veröffentlicht: (2025)

Non-crossing Hamiltonian Paths and Cycles in Output-Polynomial Time
von: Eppstein, David
Veröffentlicht: (2023)

Structure and Independence in Hyperbolic Uniform Disk Graphs
von: Bläsius, Thomas, et al.
Veröffentlicht: (2024)

O(1)-Distortion Planar Emulators for String Graphs
von: Chang, Hsien-Chih, et al.
Veröffentlicht: (2025)