• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • No language data
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Breaking Graphs into Independent Rectangles

Daniel 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