5 citations · 27 across the 31 of their papers we have counts for
6 papers · 1 filter
Shortcut Partitions in Minor-Free Graphs: Steiner Point Removal, Distance Oracles, Tree Covers, and More
Hsien-Chih Chang, Jonathan Conroy, Hung Le +3
The notion of shortcut partition, introduced recently by Chang, Conroy, Le, Milenković, Solomon, and Than [CCLMST23], is a new type of graph partition into low-diameter clusters. R…
Optimal Fault-Tolerant Spanners in Euclidean and Doubling Metrics: Breaking the Lightness Barrier
Hung Le, Shay Solomon, Cuong Than
An essential requirement of spanners in many applications is to be fault-tolerant: a -spanner of a metric space is called (vertex) -fault-tolerant (-FT) if it remains…
Resolving the Steiner Point Removal Problem in Planar Graphs via Shortcut Partitions
Hsien-Chih Chang, Jonathan Conroy, Hung Le +3
Recently the authors [CCLMST23] introduced the notion of shortcut partition of planar graphs and obtained several results from the partition, including a tree cover with tre…
Covering Planar Metrics (and Beyond): O(1) Trees Suffice
Hsien-Chih Chang, Jonathan Conroy, Hung Le +3
While research on the geometry of planar graphs has been active in the past decades, many properties of planar metrics remain mysterious. This paper studies a fundamental aspect of…
Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1
Vincent Cohen-Addad, Hung Le, Marcin Pilipczuk +1
We prove that there is a randomized polynomial-time algorithm that given an edge-weighted graph excluding a fixed-minor on vertices and an accuracy parameter $\varepsil…
VC Set Systems in Minor-free (Di)Graphs and Applications
Hung Le, Christian Wulff-Nilsen
A recent line of work on VC set systems in minor-free (undirected) graphs, starting from Li and Parter, who constructed a new VC set system for planar graphs, has given surprising…