Spelling suggestions: "subject:"tat matching"" "subject:"stat matching""
1 |
Breaking Graphs into Independent RectanglesDaniel Yu-Long Xie (19172167) 23 July 2024 (has links)
<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>
|
Page generated in 0.212 seconds