Cover Image

Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chan, Timothy M., Chang, Hsien-Chih, Gao, Jie, Kisfaludi-Bak, Sándor, Le, Hung, Zheng, Da Wei
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

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

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

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)

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

On the Approximability of the Traveling Salesman Problem with Line Neighborhoods
by: Antoniadis, Antonios, et al.
Published: (2020)

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

A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
by: Kisfaludi-Bak, Sándor, et al.
Published: (2020)

Subgraph Counting in Subquadratic Time for Bounded Degeneracy Graphs
by: Paul-Pena, Daniel, et al.
Published: (2024)

Charting the Diameter Computation Landscape on Intersection Graphs in the Plane
by: Chan, Timothy M., et al.
Published: (2026)

Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs
by: Chang, Hsien-Chih, et al.
Published: (2025)

A Subquadratic Bound for Online Bisection
by: Bienkowski, Marcin, et al.
Published: (2023)

Embedding Planar Graphs into Graphs of Treewidth $O(\log^{3} n)$
by: Chang, Hsien-Chih, et al.
Published: (2024)

Certificates in P and Subquadratic-Time Computation of Radius, Diameter, and all Eccentricities in Graphs
by: Dragan, Feodor F., et al.
Published: (2018)

Touring a Sequence of Orthogonal Polygons
by: Casel, Katrin, et al.
Published: (2026)

Weakly Approximating Knapsack in Subquadratic Time
by: Chen, Lin, et al.
Published: (2025)

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

Single-Criteria Metric $r$-Dominating Set Problem via Minor-Preserving Support
by: Browne, Reilly, et al.
Published: (2026)

Approximately Counting Knapsack Solutions in Subquadratic Time
by: Feng, Weiming, et al.
Published: (2024)

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)

Fréchet Distance in Subquadratic Time
by: Cheng, Siu-Wing, et al.
Published: (2024)

Subquadratic algorithms in minor-free digraphs: (weighted) distance oracles, decremental reachability, and more
by: Karczmarz, Adam, et al.
Published: (2024)

A Subquadratic Time Approximation Algorithm for Individually Fair k-Center
by: Ebbens, Matthijs, et al.
Published: (2024)

A Branch-and-Bound Approach for Maximum Low-Diameter Dense Subgraph Problems
by: Zhou, Yi, et al.
Published: (2025)

Gapped String Indexing in Subquadratic Space and Sublinear Query Time
by: Bille, Philip, et al.
Published: (2022)

A $(1+ε)$-Approximation for Ultrametric Embedding in Subquadratic Time
by: Bathie, Gabriel, et al.
Published: (2025)

Computing Flows in Subquadratic Space
by: Brand, Jan van den, et al.
Published: (2026)

Fast Algorithms for Graph Arboricity and Related Problems
by: Cen, Ruoxu, et al.
Published: (2025)

Distance Approximating Minors for Planar and Minor-Free Graphs
by: Chang, Hsien-Chih, et al.
Published: (2025)

Approximation Schemes for Edit Distance and LCS in Quasi-Strongly Subquadratic Time
by: Mao, Xiao, et al.
Published: (2026)

Max Cut with Small-Dimensional SDP Solutions
by: Chang, Hsien-Chih, et al.
Published: (2026)

Bounding Width on Graph Classes of Constant Diameter
by: Dabrowski, Konrad K., et al.
Published: (2025)

Fully Dynamic Algorithms for Graph Spanners via Low-Diameter Router Decomposition
by: Chuzhoy, Julia, et al.
Published: (2026)

Derandomizing Pseudopolynomial Algorithms for Subset Sum
by: Chan, Timothy M.
Published: (2026)

Streaming Edge Coloring with Subquadratic Palette Size
by: Chechik, Shiri, et al.
Published: (2023)

Improved Distance (Sensitivity) Oracles with Subquadratic Space
by: Bilò, Davide, et al.
Published: (2024)

Approximate Distance Sensitivity Oracles in Subquadratic Space
by: Bilò, Davide, et al.
Published: (2023)

Constant Approximation of Fréchet Distance in Strongly Subquadratic Time
by: Cheng, Siu-Wing, et al.
Published: (2025)

A Separator for Minor-Free Graphs Beyond the Flow Barrier
by: Le, Hung
Published: (2026)

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

Diameter Shortcut Sets on Temporal Graphs
by: Quantmeyer, Gerome
Published: (2025)