Cover Image

Maximum Independent Sets in Disk Graphs with Disks in Convex Position

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Tkachenko, Anastasiia, Wang, Haitao
Format:	Preprint
Published:	2026
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

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

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

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

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

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

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

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

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

Dynamic Connectivity in Disk Graphs
by: Baumann, Alexander, et al.
Published: (2021)

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

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)

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

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

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

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)

Approximating the Maximum Independent Set of Convex Polygons with a Bounded Number of Directions
by: Grandoni, Fabrizio, et al.
Published: (2024)

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

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

An Optimal Algorithm for Half-plane Hitting Set
by: Liu, Gang, et al.
Published: (2025)

Minimum-Weight Half-Plane Hitting Set
by: Liu, Gang, et al.
Published: (2025)

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

Online Maximum Independent Set of Hyperrectangles
by: Advani, Rishi, 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)

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

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

A Deterministic Partition Tree and Applications
by: Wang, Haitao
Published: (2025)

Algorithms for Computing Closest Points for Segments
by: Wang, Haitao
Published: (2024)

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)

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

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

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

Polynomial-Time Approximation Schemes for Independent Packing Problems on Fractionally Tree-Independence-Number-Fragile Graphs
by: Galby, Esther, et al.
Published: (2023)

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

Engineering Fully Dynamic Convex Hulls
by: van der Hoog, Ivor, et al.
Published: (2026)

Smallest Enclosing Disk Queries Using Farthest-Point Voronoi Diagrams
by: Buchin, Kevin, et al.
Published: (2026)

Online Sorting and Translational Packing of Convex Polygons
by: Aamand, Anders, et al.
Published: (2021)