In a recent paper, Hajnal, Maass, and Turaén analyzed the communication complexity of graph connectivity. Building on this work, we develop a general framework for the study of a broad class of communication problems which has several interesting special cases including the graph connectivity problem. The approach is based on the combinatorial theory of alignments and lattices.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Computer Networks and Communications
- Computational Theory and Mathematics
- Applied Mathematics