3 papers
cs.DS2026
Independence-Number Parameterized Space Complexity for Directed Connectivity Certificate
Ho-Lin Chen, Tsun Ming Cheung, Peng-Ting Lin +1
We study the space complexity of computing a sparse subgraph of a directed graph that certifies connectivity in the streaming and distributed models. Formally, for a directed graph…
cs.DS2026
Efficient Streaming Algorithms for Two-Dimensional Congruence Testing and Geometric Hashing
Yen-Cheng Chang, Tsun Ming Cheung, Meng-Tsung Tsai +1
The geometric congruence problem is a fundamental building block in many computer vision and image recognition tasks. This problem considers the decision task of whether two point…
math.CO2025
A note on plane trees with decreasing labels
Tsun-Ming Cheung, Luc Devroye, Marcel K. Goh
This note derives asymptotic upper and lower bounds for the number of planted plane trees on nodes assigned labels from the set with the restriction that on…