The communication complexity of interval orders

DOI10.1016/0166-218X(92)90019-7MaRDI QIDQ1201817zbMATH OpenOpenAlexFDO

Authors U. Faigle, Rainer Schrader, Gy. Turán

Publication date 17 January 1993

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218x(92)90019-7

zbMATH Keywords

communication complexitiescommunication complexity of interval ordersoptimal one-way protocol

Mathematics Subject Classification ID

Communication theory (94A05)

Recommendations

• Some order dimension bounds for communication complexity problems
• Publication:4678354
• Communication complexity and linearly ordered sets
• The communication complexity of the inevitable intersection problem
• On the complexity of interval orders and semiorders
• Publication:4699286
• Ordered biclique partitions and communication complexity problems
• Deterministic communication complexity of set intersection
• The Probabilistic Communication Complexity of Set Intersection

Cites work

• Interval orders without odd crowns are defect optimal
• Intransitive indifference with unequal indifference intervals
• Minimizing Setups for Ordered Sets: A Linear Algebraic Approach
• On the complexity of interval orders and semiorders

Cited in

(7)

• scientific article; zbMATH DE number 2170852 (Why is no real title available?)
• Representing interval orders by weighted bases: some complexity results
• Some order dimension bounds for communication complexity problems
• The communication complexity of interleaved group products
• Communication complexity and linearly ordered sets
• Partial orders and their convex subsets
• Tree-visibility orders

This page was built for publication: The communication complexity of interval orders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1201817)