Cuong Than

Cuong Than

Ph.D. student in Theoretical Computer Science

Publications

Matchings in Low-Arboricity Graphs in the Dynamic Graph Stream Model

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).

Towards Instance-Optimal Euclidean Spanners

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).

Optimal Euclidean Tree Covers

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).

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

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.

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

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.

Greedy Spanners in Euclidean Spaces Admit Sublinear Separators

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).

Latest Algorithms on Particular Graph Classes

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.

Schelling Models with Localized Social Influence: A Game-Theoretic Framework

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.