certificate complexity 1distributed verification 1edge connectivity 1graph connectivity 1local certification 1vertex connectivity 1
From the 1 of 3 linked papers with an AI index.
3 papers
cs.DC2026
Local Certification of Vertex and Edge Connectivity
Yi-Jun Chang, Yi-Xuan Lee, Meng-Tsung Tsai
The paper studies how to verify global vertex and edge connectivity of a graph using only local information, designing certificate schemes with provable size bounds and matching lo…
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…