Imagen de Portada

Better Diameter Algorithms for Bounded VC-dimension Graphs and Geometric Intersection Graphs

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Duraj, Lech, Konieczny, Filip, Potępa, Krzysztof
Formato:	Preprint
Publicado:	2023
Materias:	Data Structures and Algorithms Computational Geometry
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

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

Robust Algorithms for Path and Cycle Problems in Geometric Intersection Graphs
por: Marin, Malory, et al.
Publicado: (2025)

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

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

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

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

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

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

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

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

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

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

On Strong Diameter Padded Decompositions
por: Filtser, Arnold
Publicado: (2019)

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

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

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

Light Spanners with Small Hop-Diameter
por: Bhore, Sujoy, et al.
Publicado: (2025)

A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
por: Khanna, Sanjeev, et al.
Publicado: (2025)

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

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

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

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

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

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

Single-Source Shortest Paths and Almost Exact Diameter in Pseudodisk Graphs
por: de Berg, Mark, et al.
Publicado: (2026)

Diameter Computation on (Random) Geometric Graphs
por: Bläsius, Thomas, et al.
Publicado: (2026)

New Complexity and Algorithmic Bounds for Minimum Consistent Subsets
por: Banik, Aritra, et al.
Publicado: (2024)

Near-tight Bounds for Computing the Fréchet Distance in d-Dimensional Grid Graphs and the Implications for λ-low Dense Curves
por: Conradi, Jacobus, et al.
Publicado: (2026)

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

FPT Approximation Schemes for Min-Sum Radii and Min-Sum Diameters Clustering
por: Grandoni, Fabrizio, et al.
Publicado: (2026)

Counting Unit Circular Arc Intersections
por: Wang, Haitao
Publicado: (2026)

Dynamic Connectivity in Disk Graphs
por: Baumann, Alexander, et al.
Publicado: (2021)

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

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

Clustered Planarity Variants for Level Graphs
por: Fink, Simon D., et al.
Publicado: (2024)

Sparse Outerstring Graphs Have Logarithmic Treewidth
por: An, Shinwoo, et al.
Publicado: (2024)

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

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

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