collaborators

1 paper

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…