Published in SODA, 2026
We propose an algorithm constructing an approximate spanner of a planar graph. Our technique includes a novel dynamic programming.
Recommended citation: H Le, S Solomon, C Than, C Toth, T Zhang. (2026). "Approximate Light Spanners in Planar Graphs ." ACM-SIAM Symposium on Discrete Algorithms (SODA26) .
Published in STOC, 2025
We propose an algorithm constructing spanning tree cover of a bounded doubling graph. We use the output spanner to construct a light tree cover of Euclidean space, path reporting distance oracle and a routing scheme.
Recommended citation: HC Chang, J Conroy, H Le, S Solomon, C Than. (2025). "Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs ." The 57th Annual ACM Symposium on Theory of Computing (STOC) 2025.
Published in FSTTCS, 2024
We propose a three-pass algorithm finding the approximate size of the maximum mathching in a bounded arboricity graph. Our algorithm achieves space complexity $O(\sqrt{n}).$
Recommended citation: Christian Konrad, Andrew McGregor, Rik Sengupta and Cuong Than. (2024). "Matchings in Low-Arboricity Graphs in the Dynamic Graph Stream Model. " The Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024).
Published in FOCS, 2024
We propose an algorithm constructing an approximate instance-optimal spanner for Euclidean space. Our algorithm achieves optimal sparsity and lightness, with a small trade-off on the stretch.
Recommended citation: Hung Le, Shay Solomon, Cuong Than, Csaba D. Toth, Tianyi Zhang. (2024). "Towards Instance-Optimal Euclidean Spanners. " The 65th IEEE Symposium on Foundations of Computer Science (FOCS 2024).
Published in SODA, 2024
We propose an algorithm finding a solution for the Steiner point removal problem in minor-free graph
Recommended citation: HC Chang, J Conroy, H Le, L Milenkovic, S Solomon, C Than. (2024). "Shortcut partitions in minor-free graphs: Steiner point removal, distance oracles, tree covers, and more ." ACM-SIAM Symposium on Discrete Algorithms (SODA24).
Published in SoCG, 2024
We propose an algorithm constructing a (Steiner and non-Steiner) tree cover for an Euclidean point set. Our algorithm is optimal in the number of trees and running time.
Recommended citation: Hsien-Chih Chang, Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, Cuong Than. (2024). "Optimal Euclidean Tree Covers. " The 40th International Symposium on Computational Geometry (SoCG 2024).
Published in FOCS, 2023
We propose an algorithm constructing a $\epsilon$ -distortion tree cover for planar metrics of size $O_\epsilon(1)$. We also improve the embedding algorithm for planar graph into a bounded treedwidth graph with additive distortion
Recommended citation: HC Chang, J Conroy, H Le, L Milenkovic, S Solomon, C Than. (2023). "Covering Planar Metrics (and Beyond): O(1) Trees Suffice ." The 64th IEEE Symposium on Foundations of Computer Science (FOCS) 2023.
Published in FOCS, 2023
We propose an algorithm constructing a Vertex-Fault-Tolerant spanner of a set of points in doubling space. Our algorithm is optimal in term of lightness, sparsity, maximum degree and running time.
Recommended citation: H Le, S Solomon, C Than. (2023). "Optimal Fault-Tolerant Spanners in Euclidean and Doubling Metrics: Breaking the Ω(log n) Lightness Barrier ." The 64th IEEE Symposium on Foundations of Computer Science (FOCS) 2023.
Published in SODA, 2022
We prove that greedy spanners admit sublinear separator in Euclidean Spaces. Moreover, we extend the result to bound doubling dimension spaces. We prove that there exists a spanner with sublinear separator and bounded degree. This resolves an open question from 2010.
Recommended citation: H Le, C Than. (2021). "Greedy Spanners in Euclidean Spaces Admit Sublinear Separators ." The 33rd ACM-SIAM Symposium on Discrete Algorithms (SODA22).
Published in IOI Journal, 2020
This paper is about algorithms solving maximum induced matching and its application in competitive programming.
Recommended citation: T Do, T Pham, C Than. (2020). "Latest Algorithms on Particular Graph Classes." IOI Journal.
Published in AAMAS, 2020
This paper is about game theory: Schelling Models with Localized Social Influence.
Recommended citation: H Chan, M Irfan and C Than, "Schelling Models with Localized Social Influence: A Game-Theoretic Framework." The 19th International Conference on Autonomous Agents and MultiAgent Systems.
Published in ACDT, 2018
This paper is about maximum induced matching problem in permutation graphs.
Recommended citation: C Than, T Do. (2018). "An O (n√ n log log n) average case algorithm for the maximum induced matching problem in permutation graphs ." 2018 5th Asian Conference on Defense Technology (ACDT).