<p>We survey the problem of covering and partitioning a bipartite graph using vertex-disjoint unions of bicliques. The concept of a vertex-disjoint union of bicliques has been given many names in computer science: it has been termed a blocky matrix in communication complexity,</p>
<p>a fat matching in circuit complexity, a bipartite P4-free graph in graph theory, a simple graph in cryptography, and a bicluster in bioinformatics. We aim to unify all of these perspectives, compiling what is known and unknown about the problem, including discussion on upper and lower bounding techniques for the problem, bounds for specific families of graphs, and</p>
<p>the hardness of computation of the problem. Along the way, we present a new explicit graph for which the covering and partitioning numbers are different.</p>
| Identifer | oai:union.ndltd.org:purdue.edu/oai:figshare.com:article/26352283 |
| Date | 23 July 2024 |
| Creators | Daniel Yu-Long Xie (19172167) |
| Source Sets | Purdue University |
| Detected Language | English |
| Type | Text, Thesis |
| Rights | CC BY 4.0 |
| Relation | https://figshare.com/articles/thesis/Breaking_Graphs_into_Independent_Rectangles/26352283 |
Page generated in 0.0018 seconds