Hung Le

activity

20242026

most citedOptimal Padded Decomposition For Bounded Treewidth Graphs

2 citations · 3 across the 8 of their papers we have counts for

collaborators

11 papers

cs.DS2026

Three trees suffice for a constant stretch in minor-free graphs

Hung Le, Huy Pham, Cuong Than +1

In this short note, we show that $H$ -minor-free graphs have a tree cover with $3$ trees and constant stretch for any fixed graph $H$ . The number of trees matches the recent lower b…

cs.CG2026

Improved Euclidean Shallow Light Trees

Hung Le, Shay Solomon, Cuong Than +2

For parameters $α, β \geq 1$ , a spanning tree $T$ of a weighted graph $G$ rooted at a designated vertex $r$ is called an $(α, β)$ -shallow-light tree (SLT) if (i) for every vertex $v$ ,…

cs.DS2026

Planar Embedding of Okamura-Seymour Quasimetrics in Polynomial Time with an Application to Distributed SSSP

Hung Le, Hector Tierno, Shuang Yang

A quasi-metric $(T, δ_{T})$ is an Okamura-Seymour quasimetric if there exists an edge-weighted planar embedded directed graph $G = (V, E, w)$ such that $T$ is a set of terminals on the…

cs.CG2026★ 1 cited

Fine-Grained Complexity of Continuous Euclidean k-Center

Lotte Blank, Karl Bringmann, Parinya Chalermsook +4

In the (continuous) Euclidean $k$ -center problem, given $n$ points in $R^{d}$ and an integer $k$ , the goal is to find $k$ center points in $R^{d}$ that minimize the m…

cs.CG2026

A Polynomial Coreset for Furthest Neighbor in Planar Metrics

Kacper Kluk, Hung Le, Wojciech Nadara +3

A furthest neighbor data structure on a metric space $(V, dist)$ and a set $P \subseteq V$ answers the following query: given $v \in V$ , output $p \in P$ maximizing $\mathr…

cs.CG2025

Approximating Euclidean Shallow-Light Trees

Hung Le, Shay Solomon, Cuong Than +2

For a weighted graph $G = (V, E, w)$ and a designated source vertex $s \in V$ , a spanning tree that simultaneously approximates a shortest-path tree w.r.t. source $s$ and a minimum…

cs.DS2025

Tree-Like Shortcuttings of Trees

Hung Le, Lazar Milenković, Shay Solomon +1

Sparse shortcuttings of trees -- equivalently, sparse 1-spanners for tree metrics with bounded hop-diameter -- have been studied extensively (under different names and settings), s…

cs.CG2025

Covering the Euclidean Plane by a Pair of Trees

Hung Le, Lazar Milenković, Shay Solomon +1

A { $t$ -stretch tree cover} of a metric space $M = (X, δ)$ , for a parameter $t \geq 1$ , is a collection of trees such that every pair of points has a $t$ -stretch path in one of the tr…

cs.CG2025

Optimal Bounds for Spanners and Tree Covers in Doubling Metrics

An La, Hung Le, Shay Solomon +4

It is known that any $n$ -point set in the $d$ -dimensional Euclidean space $R^{d}$ , for $d = O (1)$ , admits: 1) a $(1 + ε)$ -spanner with maximum degree $O ~ (ε^{- d + 1})$ and…

cs.DS2025

Approximate Light Spanners in Planar Graphs

Hung Le, Shay Solomon, Cuong Than +2

In their seminal paper, Althöfer et al. (DCG 1993) introduced the {\em greedy spanner} and showed that, for any weighted planar graph $G$ , the weight of the greedy $(1 + ε)$ -spanner…

cs.DS2024★ 2 cited

Optimal Padded Decomposition For Bounded Treewidth Graphs

Arnold Filtser, Tobias Friedrich, Davis Issac +4

A $(β, δ, Δ)$ -padded decomposition of an edge-weighted graph $G = (V, E, w)$ is a stochastic decomposition into clusters of diameter at most $Δ$ such that for every vertex $v \in V$ , th…