Cover Image

Robust Algorithms for Path and Cycle Problems in Geometric Intersection Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Marin, Malory, Raymond, Jean-Florent, Watrigant, Rémi
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Computational Geometry
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Small Independent Sets versus Small Separator in Geometric Intersection Graphs
by: Marin, Malory, et al.
Published: (2026)

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

Channel allocation revisited through 1-extendability of graphs
by: Busson, Anthony, et al.
Published: (2024)

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

On Subexponential Parameterized Algorithms for Steiner Tree on Intersection Graphs of Geometric Objects
by: Bhore, Sujoy, et al.
Published: (2025)

Subexponential algorithms in geometric graphs via the subquadratic grid minor property: the role of local radius
by: Berthe, Gaétan, 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)

Approximation Schemes for Subset TSP and Steiner Tree on Geometric Intersection Graphs
by: Kisfaludi-Bak, Sándor, et al.
Published: (2026)

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

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

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

Approximation Algorithms for Smallest Intersecting Balls
by: Zheng, Jiaqi, et al.
Published: (2024)

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)

Non-crossing Hamiltonian Paths and Cycles in Output-Polynomial Time
by: Eppstein, David
Published: (2023)

Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and Matching
by: Bhore, Sujoy, et al.
Published: (2024)

Range Counting Oracles for Geometric Problems
by: Driemel, Anne, et al.
Published: (2025)

Online Algorithms for Geometric Independent Set
by: De, Minati, et al.
Published: (2026)

An Algorithmic Solution for Computing Circle Intersection Areas and its Applications to Wireless Communications
by: Librino, Federico, et al.
Published: (2012)

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

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

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

Algorithms for Halfplane Coverage and Related Problems
by: Wang, Haitao, et al.
Published: (2024)

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

Algorithms for Distance Problems in Continuous Graphs
by: Cabello, Sergio, et al.
Published: (2025)

Improved Online Hitting Set Algorithms for Structured and Geometric Set Systems
by: Bhore, Sujoy, et al.
Published: (2026)

Improved Algorithms for Distance Selection and Related Problems
by: Wang, Haitao, et al.
Published: (2023)

Counting Unit Circular Arc Intersections
by: Wang, Haitao
Published: (2026)

Subexponential and Parameterized Mixing Times of Glauber Dynamics on Independent Sets
by: Marin, Malory
Published: (2025)

An Improved FPT Algorithm for Computing the Interleaving Distance between Merge Trees via Path-Preserving Maps
by: P V, Althaf, et al.
Published: (2026)

A Quasi-Polynomial Time Algorithm for 3-Coloring Circle Graphs
by: S, Ajaykrishnan E, et al.
Published: (2025)

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

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

Reconstructing Riemannian Metrics From Random Geometric Graphs
by: Huang, Han, et al.
Published: (2025)

Using Ray-shooting Queries for Sublinear Algorithms for Dominating Sets in RDV Graphs
by: Biedl, Therese, et al.
Published: (2026)

Enclosing Points with Geometric Objects
by: Chan, Timothy M., et al.
Published: (2024)

Uncrossed Multiflows and Applications to Disjoint Paths
by: Chekuri, Chandra, et al.
Published: (2025)

Shortest Paths on Convex Polyhedral Surfaces
by: Wang, Haitao
Published: (2025)

Dynamic Convex Hulls for Simple Paths
by: Brewer, Bruce, et al.
Published: (2024)

Continuous Map Matching to Paths under Travel Time Constraints
by: Bosch, Yannick, et al.
Published: (2025)