8 papers
Can LLMs be Used to Simplify Algorithms? Simpler Algorithms for Vertex Coloring and Edge Connectivity
Antoine El-Hayek, Monika Henzinger, Da Wei Zheng
Having simple algorithms is important for the practical adoption of new algorithms. However, simplifying existing algorithms is a field that does not usually receive a lot of atten…
Real-weighted Diameter and Eccentricity of Minor-free and Bounded VC-dimension Graphs in Truly Subquadratic Time
Da Wei Zheng
We present the first truly subquadratic time algorithm to compute diameter and eccentricity in real-weighted directed graphs with constant distance VC-dimension and strongly sublin…
Cutting Planarians: Planar Emulators for String Graphs
Hsien-Chih Chang, Jonathan Conroy, Zihan Tan +1
In this paper we construct distance sketches for intersection graphs of arbitrary path-connected regions in the plane (known as the string graphs) in the constant and $1+\varepsilo…
Charting the Diameter Computation Landscape on Intersection Graphs in the Plane
Timothy M. Chan, Hsien-Chih Chang, Jie Gao +3
Computing the diameter of the intersection graphs of objects is a basic problem in computational geometry. Previous works showed that the complexity of computing the diameter mainl…
DAG Covers: The Steiner Point Effect
Sujoy Bhore, Hsien-Chih Chang, Jonathan Conroy +4
Given a weighted digraph , a -DAG cover is a collection of dominating DAGs such that all distances are approximately preserved: for every pair $(u,…
Charting the Diameter Computation Landscape of Geometric Intersection Graphs in Three Dimensions and Higher
Timothy M. Chan, Hsien-Chih Chang, Jie Gao +3
Recent research on computing the diameter of geometric intersection graphs has made significant strides, primarily focusing on the 2D case where truly subquadratic-time algorithms…