论文标题
查找共同图形的双分区
Finding Biclique Partitions of Co-Chordal Graphs
论文作者
论文摘要
图$ G $的Biclique分区编号$（\ text {bp}）$称为完全覆盖图表边缘所需的最少数量的完整双分（Biclique）子图。在本文中，我们表明，双式分区编号（$ \ text {bp} $）的共同关系（弦的互补图）图$ g =（v，e）$小于最大块的数量（$ \ \ \ \ \ \ text {mc} $）的互补图形：Chordary Graph：conordary Graph：chordorary Graph：一个Chordal图形：我们首先提供了一个``划分和征服''的启发式的一般框架，该启发式方法是基于Clique Trees的共同图形的最小双式分区。此外，复杂性$ o [| V |（| V |+| e^C |）的复杂性启发式均可通过将词汇范围的搜索置于词汇范围内搜索。 $ g $带$ \ text {mc}（g^c）-1 $。 \ text {mc}（g^c） - 1 $如果$ g $是拆分图。
The biclique partition number $(\text{bp})$ of a graph $G$ is referred to as the least number of complete bipartite (biclique) subgraphs that are required to cover the edges of the graph exactly once. In this paper, we show that the biclique partition number ($\text{bp}$) of a co-chordal (complementary graph of chordal) graph $G = (V, E)$ is less than the number of maximal cliques ($\text{mc}$) of its complementary graph: a chordal graph $G^c = (V, E^c)$. We first provide a general framework of the ``divide and conquer" heuristic of finding minimum biclique partitions of co-chordal graphs based on clique trees. Furthermore, a heuristic of complexity $O[|V|(|V|+|E^c|)]$ is proposed by applying lexicographic breadth-first search to find structures called moplexes. Either heuristic gives us a biclique partition of $G$ with size $\text{mc}(G^c)-1$. In addition, we prove that both of our heuristics can solve the minimum biclique partition problem on $G$ exactly if its complement $G^c$ is chordal and clique vertex irreducible. We also show that $\text{mc}(G^c) - 2 \leq \text{bp}(G) \leq \text{mc}(G^c) - 1$ if $G$ is a split graph.
