5 citations · 9 across the 9 of their papers we have counts for
10 papers · 1 filter
Optimal Approximate Distance Oracle for Planar Graphs
Hung Le, Christian Wulff-Nilsen
A -approximate distance oracle of an edge-weighted graph is a data structure that returns an approximate shortest path distance between any two query vertices up to a $(1+ε)…
Near-Optimal Spanners for General Graphs in (Nearly) Linear Time
Hung Le, Shay Solomon
Let be a weighted undirected graph on vertices and edges, let be any integer, and let be any parameter. We present the following…
Clan Embeddings into Trees, and Low Treewidth Graphs
Arnold Filtser, Hung Le
In low distortion metric embeddings, the goal is to embed a host "hard" metric space into a "simpler" target space while approximately preserving pairwise distances. A highly desir…
On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs
Vincent Cohen-Addad, Arnold Filtser, Philip N. Klein +1
Understanding the structure of minor-free metrics, namely shortest path metrics obtained over a weighted graph excluding a fixed minor, has been an important research direction sin…
Designing Practical PTASes for Minimum Feedback Vertex Set in Planar Graphs
Glencora Borradaile, Hung Le, Baigong Zheng
We present two algorithms for the minimum feedback vertex set problem in planar graphs: an PTAS using a linear kernel and balanced separator, and a heuristic algorith…
Local Search is a PTAS for Feedback Vertex Set in Minor-free Graphs
Hung Le, Baigong Zheng
We show that a simple local search gives a PTAS for the Feedback Vertex Set (FVS) problem in minor-free graphs. An efficient PTAS in minor-free graphs was known for this problem by…