Ordered biclique partitions and communication complexity problems

DOI10.1016/j.dam.2014.10.029zbMath1311.05167arXiv1311.6192OpenAlexW2963309684MaRDI QIDQ2342387

Kazuyuki Amano, Manami Shigeta

Publication date: 28 April 2015

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

Full work available at URL: https://arxiv.org/abs/1311.6192

zbMATH Keywords

rankcomplete graphsBoolean matrixbiclique partitionfooling set

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (6)

Around the log-rank conjecture ⋮ Finding biclique partitions of co-chordal graphs ⋮ On the binary and Boolean rank of regular matrices ⋮ Decomposition techniques applied to the clique-stable set separation problem ⋮ Unnamed Item ⋮ Communication Complexity of Pairs of Graph Families with Applications

Cites Work

• Unnamed Item
• Unnamed Item
• Clique versus independent set
• A counterexample to the Alon-Saks-Seymour conjecture and related problems
• On covering graphs by complete bipartite subgraphs
• The linear-array conjecture in communication complexity is false
• Expressing combinatorial optimization problems by linear programs
• A comparison of two lower-bound methods for communication complexity
• Fooling-sets and rank
• Some improved bounds on communication complexity via new decomposition of cliques
• Communication Complexity
• On the complexity of communication complexity

This page was built for publication: Ordered biclique partitions and communication complexity problems