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 条
  • [21] Decomposition of complete bipartite graphs into generalized prisms
    Cichacz, Sylwia
    Froncek, Dalibor
    Kovar, Petr
    EUROPEAN JOURNAL OF COMBINATORICS, 2013, 34 (01) : 104 - 110
  • [22] PLANAR DECOMPOSITION OF A CLASS OF COMPLETE BIPARTITE GRAPHS
    SHIRAKAW.I
    TAKAHASH.H
    OZAKI, H
    ELECTRONICS & COMMUNICATIONS IN JAPAN, 1968, 51 (10): : 1 - &
  • [23] Minimal path decomposition of complete bipartite graphs
    Constantinou, Costas K.
    Ellinas, Georgios
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2018, 35 (03) : 684 - 702
  • [24] DECOMPOSITION OF PRODUCT GRAPHS INTO COMPLETE BIPARTITE SUBGRAPHS
    REZNICK, B
    TIWARI, P
    WEST, DB
    DISCRETE MATHEMATICS, 1985, 57 (1-2) : 189 - 193
  • [25] Minimal path decomposition of complete bipartite graphs
    Costas K. Constantinou
    Georgios Ellinas
    Journal of Combinatorial Optimization, 2018, 35 : 684 - 702
  • [26] EIGENSHARP GRAPHS - DECOMPOSITION INTO COMPLETE BIPARTITE SUBGRAPHS
    KRATZKE, T
    REZNICK, B
    WEST, D
    TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1988, 308 (02) : 637 - 653
  • [27] Towards Distributed Bitruss Decomposition on Bipartite Graphs
    Wang, Yue
    Xu, Ruiqi
    Jian, Xun
    Zhou, Alexander
    Chen, Lei
    PROCEEDINGS OF THE VLDB ENDOWMENT, 2022, 15 (09): : 1889 - 1901
  • [28] DECOMPOSITION OF BIPARTITE GRAPHS UNDER DEGREE CONSTRAINTS
    BROERSMA, HJ
    FAUDREE, RJ
    VANDENHEUVEL, J
    VELDMAN, HJ
    NETWORKS, 1993, 23 (03) : 159 - 164
  • [29] Decomposition of complete bipartite graphs into paths and cycles
    Jeevadoss, S.
    Muthusamy, A.
    DISCRETE MATHEMATICS, 2014, 331 : 98 - 108
  • [30] Odd Star Decomposition of Complete Bipartite Graphs
    Purwanto
    Winanthi, Fryska Ayu
    3RD INTERNATIONAL CONFERENCE ON MATHEMATICS AND SCIENCE EDUCATION (ICOMSE) 2019: STRENGTHENING MATHEMATICS AND SCIENCE EDUCATION RESEARCH FOR THE CHALLENGE OF GLOBAL SOCIETY, 2020, 2215
12345