The communication complexity of interval orders

Share/Save/Bookmark

Faigle, Ulrich and Schrader, Rainer and Turan, Gyorgy (1992) The communication complexity of interval orders. Discrete Applied Mathematics, 40 (1). pp. 19-28. ISSN 0166-218X

open access
[img]
Preview
PDF
645kB
Abstract:The communication complexity of interval orders is studied within the following model. Two players choose two elements x and y and want to determine whether x<y holds by exchanging as few bits of information as possible. It is shown that an optimal one-way protocol exists by first establishing a rank-optimality result for a subclass of generalized interval orders. It turns out that the deterministic and nondeterministic communication complexities coincide for generalized interval orders. The analogous statement for the complementary relation is true for interval orders in the strict sense while it need not hold for generalized interval orders.
Item Type:Article
Copyright:© 1992 Elsevier Science
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/29864
Official URL:http://dx.doi.org/10.1016/0166-218X(92)90019-7
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 140498