Electronic Resource
Springer
Acta informatica
28 (1991), S. 593-601
ISSN:
1432-0525
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Summary We associate with a general (0, 1)-matrixM an ordered setP(M) and derive lower and upper bounds for the deterministic communication complexity ofM in terms of the order dimension ofP(M). We furthermore consider the special class of communication matricesM obtained as cliques vs. stable sets incidence matrices of comparability graphsG. We bound their complexity byO((logd)·(logn)), wheren is the number of nodes ofG andd is the order dimension of an orientation ofG. In this special case, our bound is shown to improve other well-known bounds obtained for the general cliques vs. stable set problem.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01463947
Permalink
|
Location |
Call Number |
Expected |
Availability |