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 Congruence Hashing
Yen-Cheng Chang, Tsun Ming Cheung, Meng-Tsung Tsai +1
Geometric congruence asks whether two point multisets are identical up to translation and rotation, while congruence hashing seeks compact encodings that support efficient congruen…
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…