2 citations · 4 across the 12 of their papers we have counts for
7 papers · 1 filter
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 -minor-free graphs have a tree cover with trees and constant stretch for any fixed graph . The number of trees matches the recent lower b…
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…
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 , the weight of the greedy -spanner…
Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs
Hsien-Chih Chang, Jonathan Conroy, Hung Le +2
A -stretch tree cover of an edge-weighted -vertex graph is a collection of trees, where every pair of vertices has a -stretch path in one o…
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…
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…