Bimodular decomposition of bipartite graphs

被引：0
|
作者：
Fouquet, JL [1 ]
Habib, M
de Montgolfier, F
Vanherpe, JM
机构：
[1] Univ Maine, Orono, ME 04469 USA
[2] Univ Montpellier 2, LIRMM, F-34095 Montpellier 5, France
[3] Univ Paris 07, LIAFA, F-75221 Paris 05, France
来源：
GRAPH -THEORETIC CONCEPTS IN COMPUTER SCIENCE | 2004年 / 3353卷
关键词：
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
This paper gives a decomposition theory for bipartite graphs. It uses bimodules, a special case of 2-modules (also known as homogeneous pairs, an extension of both modules and splits). It is shown how a unique decomposition tree represents the bimodular decomposition of a bipartite graph, with strong analogs with modular decomposition of graphs. An O(mn(3)) algorithm for this decomposition is provided. At least a classification of the 2-modules of a bipartite graph is given.
引用
收藏
页码：117 / 128
页数：12
相关论文
共 50 条
  • [1] On the decomposition of graphs into complete bipartite graphs
    Dong, Jinquan
    Liu, Yanpei
    GRAPHS AND COMBINATORICS, 2007, 23 (03) : 255 - 262
  • [2] On the Decomposition of Graphs into Complete Bipartite Graphs
    Jinquan Dong
    Yanpei Liu
    Graphs and Combinatorics, 2007, 23 : 255 - 262
  • [3] Decomposition of complete bipartite graphs
    VandenEynden, C
    ARS COMBINATORIA, 1997, 46 : 287 - 296
  • [4] DECOMPOSITION OF BIPARTITE GRAPHS INTO PATHS
    CHILAKAMARRI, KB
    AMERICAN MATHEMATICAL MONTHLY, 1988, 95 (07): : 634 - 636
  • [5] Bipartite decomposition of random graphs
    Alon, Noga
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2015, 113 : 220 - 235
  • [6] On the cyclic decomposition of circulant graphs into bipartite graphs
    Bunge, Ryan C.
    El-Zanati, Saad I.
    Rumsey, Chepina
    Eynden, Charles Vanden
    AUSTRALASIAN JOURNAL OF COMBINATORICS, 2013, 56 : 201 - 217
  • [7] DECOMPOSITION OF RANDOM GRAPHS INTO COMPLETE BIPARTITE GRAPHS
    Chung, Fan
    Peng, Xing
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2016, 30 (01) : 296 - 310
  • [8] Core Decomposition and Maintenance in Bipartite Graphs
    Yu, Dongxiao
    Zhang, Lifang
    Luo, Qi
    Cheng, Xiuzhen
    Cai, Zhipeng
    TSINGHUA SCIENCE AND TECHNOLOGY, 2023, 28 (02): : 292 - 309
  • [9] Decomposition of bipartite graphs into closed trails
    Cichacz, Sylwia
    Hornak, Mirko
    CZECHOSLOVAK MATHEMATICAL JOURNAL, 2009, 59 (01) : 129 - 144
  • [10] On the complete bipartite decomposition of planar graphs
    Dong, JQ
    Liu, YP
    UTILITAS MATHEMATICA, 2000, 57 : 33 - 42
12345