5 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…
Planar Embedding of Okamura-Seymour Quasimetrics in Polynomial Time with an Application to Distributed SSSP
Hung Le, Hector Tierno, Shuang Yang
A quasi-metric is an Okamura-Seymour quasimetric if there exists an edge-weighted planar embedded directed graph such that is a set of terminals on the…
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 -spanne…
Optimal Padded Decomposition For Bounded Treewidth Graphs
Arnold Filtser, Tobias Friedrich, Davis Issac +4
A -padded decomposition of an edge-weighted graph is a stochastic decomposition into clusters of diameter at most such that for every vertex …