TY - JOUR
T1 - Communication complexity and combinatorial lattice theory
AU - Lovǎsz, Laészloé
AU - Saks, Michael
N1 - Funding Information: * Supported in part by NSF Grants DMS87 03541, CCR89-11388 and Air Force Office of Scientific Research Grant AFOSR-0271.
PY - 1993
Y1 - 1993
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=25544437705&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=25544437705&partnerID=8YFLogxK
U2 - https://doi.org/10.1016/0022-0000(93)90035-U
DO - https://doi.org/10.1016/0022-0000(93)90035-U
M3 - Article
VL - 47
SP - 322
EP - 349
JO - Journal of Computer and System Sciences
JF - Journal of Computer and System Sciences
SN - 0022-0000
IS - 2
ER -