Hung Le

collaborators

Showing cs.DSShow all

3 papers · 1 filter

cs.DS2025

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

Timothy M. Chan, Hsien-Chih Chang, Jie Gao +3

We give the first truly subquadratic time algorithm, with $O^{*} (n^{2 - 1/18})$ running time, for computing the diameter of an $n$ -vertex unit-disk graph, resolving a central open prob…

cs.DS2025

Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs

Hsien-Chih Chang, Jonathan Conroy, Hung Le +2

A $(1 + ε)$ -stretch tree cover of an edge-weighted $n$ -vertex graph $G$ is a collection of trees, where every pair of vertices has a $(1 + ε)$ -stretch path in one o…

cs.DS2024

Embedding Planar Graphs into Graphs of Treewidth $O (lo g^{3} n)$

Hsien-Chih Chang, Vincent Cohen-Addad, Jonathan Conroy +3

Cohen-Addad, Le, Pilipczuk, and Pilipczuk [CLPP23] recently constructed a stochastic embedding with expected $1 + ε$ distortion of $n$ -vertex planar graphs (with polynomial…

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

Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs

Embedding Planar Graphs into Graphs of Treewidth O(log3n)

Embedding Planar Graphs into Graphs of Treewidth $O (lo g^{3} n)$