Hung Le

CoRR, 2024

VC Set Systems in Minor-free (Di)Graphs and Applications.

[BibT_eX]

[DOI]

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Shortcut Partitions in Minor-Free Graphs: Steiner Point Removal, Distance Oracles, Tree Covers, and More.

[BibT_eX]

[DOI]

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

2023

Resolving the Steiner Point Removal Problem in Planar Graphs via Shortcut Partitions.

[BibT_eX]

[DOI]

CoRR, 2023

A Unified Framework for Light Spanners.

[BibT_eX]

[DOI]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Approximate Distance Oracles for Planar Graphs with Subpolynomial Error Dependency.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Optimal Fault-Tolerant Spanners in Euclidean and Doubling Metrics: Breaking the Ω (log n) Lightness Barrier.

[BibT_eX]

[DOI]

Cuong Than

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Covering Planar Metrics (and Beyond): O(1) Trees Suffice.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Sparse Euclidean Spanners with Optimal Diameter: A General and Robust Lower Bound via a Concave Inverse-Ackermann Function.

[BibT_eX]

[DOI]

Lazar Milenkovic

Proceedings of the 39th International Symposium on Computational Geometry, 2023

2022

Locality-sensitive orderings and applications to reliable spanners.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Greedy Spanners in Euclidean Spaces Admit Sublinear Separators.

[BibT_eX]

[DOI]

Cuong Than

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Near-Optimal Spanners for General Graphs in (Nearly) Linear Time.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Can't See the Forest for the Trees: Navigating Metric Spaces by Bounded Hop-Diameter Spanners.

[BibT_eX]

[DOI]

Proceedings of the PODC '22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25, 2022

Dynamic Matching Algorithms Under Vertex Updates.

[BibT_eX]

[DOI]

Lazar Milenkovic

Virginia Vassilevska Williams

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Low Treewidth Embeddings of Planar and Minor-Free Metrics.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Sparse Euclidean Spanners with Tiny Diameter: A Tight Lower Bound.

[BibT_eX]

[DOI]

Lazar Milenkovic

Proceedings of the 38th International Symposium on Computational Geometry, 2022

2021

A Unified Framework of Light Spanners II: Fine-Grained Optimality.

[BibT_eX]

[DOI]

CoRR, 2021

Towards a Unified Theory of Light Spanners I: Fast (Yet Optimal) Constructions.

[BibT_eX]

[DOI]

CoRR, 2021

Reliable Spanners: Locality-Sensitive Orderings Strike Back.

[BibT_eX]

[DOI]

CoRR, 2021

Clan embeddings into trees, and low treewidth graphs.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Optimal Approximate Distance Oracle for Planar Graphs.

[BibT_eX]

[DOI]

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

Local search is a PTAS for feedback vertex set in minor-free graphs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2020

A Unified and Fine-Grained Approach for Light Spanners.

[BibT_eX]

[DOI]

CoRR, 2020

A PTAS for subset TSP in minor-free graphs.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Light Euclidean Spanners with Steiner Points.

[BibT_eX]

[DOI]

Proceedings of the 28th Annual European Symposium on Algorithms, 2020

2019

Greedy spanners are optimal in doubling metrics.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Engineering a PTAS for Minimum Feedback Vertex Set in Planar Graphs.

[BibT_eX]

[DOI]

Proceedings of the Analysis of Experimental Algorithms - Special Event, 2019

Truly Optimal Euclidean Spanners.

[BibT_eX]

[DOI]

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

A Simple Local Search Gives a PTAS for the Feedback Vertex Set Problem in Minor-Free Graphs.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics - 25th International Conference, 2019

2018

A Better Bound on the Largest Induced Forests in Triangle-Free Planar Graph.

[BibT_eX]

[DOI]

Graphs Comb., 2018

Designing Practical PTASes for Minimum Feedback Vertex Set in Planar Graphs.

[BibT_eX]

[DOI]

CoRR, 2018

2017

Large Induced Acyclic and Outerplanar Subgraphs of 2-Outerplanar Graph.

[BibT_eX]

[DOI]

Melissa Sherman-Bennett

Graphs Comb., 2017

Light spanners for bounded treewidth graphs imply light spanners for $H$-minor-free graphs.

[BibT_eX]

[DOI]

CoRR, 2017

Embedded-width: A variant of treewidth for plane graphs.

[BibT_eX]

[DOI]

CoRR, 2017

Minor-Free Graphs Have Light Spanners.

[BibT_eX]

[DOI]

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016

Optimal Dynamic Program for r-Domination Problems over Tree Decompositions.

[BibT_eX]

[DOI]