Sitemap

A list of all the posts and pages found on the site. For you robots out there is an XML version available for digesting as well.

Page Not Found

Page not found. Your pixels are in another canvas.

Jupyter notebook markdown generator

Posts

publications

An O (n√ n log log n) average case algorithm for the maximum induced matching problem in permutation graphs

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). https://thanvietcuong.github.io/files/mim_permutation_graph.pdf

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. https://thanvietcuong.github.io/files/Schelling_AAMAS2020.pdf

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. https://thanvietcuong.github.io/files/lastest_algo_graph_ioi.pdf

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). https://arxiv.org/abs/2107.06490

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

Published in arXiv, 2023

We show that every planar graph admits a distance-preserving minor with constant distortion, resolving the Steiner Point Removal problem for planar graphs.

Recommended citation: Hsien-Chih Chang, Jonathan Conroy, Hung Le, Lazar Milenković, Shay Solomon, Cuong Than. (2023). "Resolving the Steiner Point Removal Problem in Planar Graphs via Shortcut Partitions." arXiv:2306.06235. https://arxiv.org/pdf/2306.06235

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. https://arxiv.org/pdf/2306.11226.pdf

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. https://arxiv.org/pdf/2306.06215.pdf

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). https://arxiv.org/pdf/2403.17754

Shortcut partitions in minor-free graphs: Steiner point removal, distance oracles, tree covers, and more

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). https://arxiv.org/abs/2308.00555

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). https://arxiv.org/pdf/2409.08227

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). https://drops.dagstuhl.de/storage/00lipics/lipics-vol323-fsttcs2024/LIPIcs.FSTTCS.2024/LIPIcs.FSTTCS.2024.pdf#page=579

Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs

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. https://arxiv.org/pdf/2503.22669

Approximate Light Spanners in Planar Graphs

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) . https://arxiv.org/pdf/2505.24825

Approximating Euclidean Shallow-Light Trees

Published in SoCG, 2026

We propose a bicriteria algorithm finding an approximate shallow-light tree of an Euclidean point set.

Recommended citation: H Le, S Solomon, C Than, C Tóth and T Zhang. (2026). "Approximating Euclidean Shallow-Light Trees ." The 42th International Symposium on Computational Geometry, (SoCG) 2026. https://arxiv.org/pdf/2512.10797

Optimal Bounds for Spanners and Tree Covers in Doubling Metrics

Published in SoCG, 2026

We propose a lower bound for sparsity and lightness of spanners in doubling metrics.

Recommended citation: A La, H Le, S Solomon, C Than, Vinayak, S Yang and T Zhang. (2026). "Optimal Bounds for Spanners and Tree Covers in Doubling Metrics ." The 42th International Symposium on Computational Geometry, (SoCG) 2026. https://arxiv.org/pdf/2508.11555

Tree-Like Shortcuttings of Trees

Published in SoCG, 2026

We propose an algorithm embedding a tree metric to a metric of bounded hop-diameter and bounded treewidth or arboricity

Recommended citation: H Le, S Solomon, L Milenkovic and C Than. (2026). "Tree-Like Shortcuttings of Trees." The 42th International Symposium on Computational Geometry, (SoCG) 2026. https://arxiv.org/pdf/2510.14918

Three Trees Suffice for a Constant Stretch in Minor-Free Graphs

Published in arXiv, 2026

Download paper here

Recommended citation: Hung Le, Huy Pham, Cuong Than, Tuan Tran. (2026). "Three Trees Suffice for a Constant Stretch in Minor-Free Graphs." arXiv:2608.13508. https://arxiv.org/pdf/2608.13508

Improved Euclidean Shallow-Light Trees

Published in SODA, 2027

We give improved constructions of shallow-light trees for Euclidean point sets.

Recommended citation: Hung Le, Shay Solomon, Cuong Than, Csaba D. Tóth, Tianyi Zhang. (2027). "Improved Euclidean Shallow-Light Trees." ACM-SIAM Symposium on Discrete Algorithms (SODA 2027). https://arxiv.org/pdf/2608.03951