On maximum induced matchings in bipartite graphs

被引：67
|
作者：
Lozin, VV [1 ]
机构：
[1] Rutgers State Univ, RUTCOR, Piscataway, NJ 08854 USA
来源：
INFORMATION PROCESSING LETTERS | 2002年 / 81卷 / 01期
关键词：
graph algorithms; computational complexity; maximum induced matching; bipartite graphs;
D O I：
10.1016/S0020-0190(01)00185-5
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
The problem of finding a maximum induced matching is known to be NP-hard in general bipartite graphs. We strengthen this result by reducing the problem to some special classes of bipartite graphs such as bipartite graphs with maximum degree 3 or C-4-free bipartite graphs. On the other hand, we describe a new polynomially solvable case for the problem in bipartite graphs which deals with a generalization of bi-complement reducible graphs. (C) 2002 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：7 / 11
页数：5
相关论文
共 50 条
  • [1] New results on maximum induced matchings in bipartite graphs and beyond
    Dabrowski, Konrad K.
    Demange, Marc
    Lozin, Vadim V.
    THEORETICAL COMPUTER SCIENCE, 2013, 478 : 33 - 40
  • [2] INDUCED MATCHINGS IN GRAPHS OF BOUNDED MAXIMUM DEGREE
    Joos, Felix
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2016, 30 (03) : 1876 - 1882
  • [3] Maximal and maximum induced matchings in connected graphs
    Yuan, Bo-Jun
    Yang, Zhao-Yu
    Zheng, Lu
    Gong, Shi-Cai
    APPLIED MATHEMATICS AND COMPUTATION, 2025, 500
  • [4] ACYCLIC MATCHINGS IN SUBCLASSES OF BIPARTITE GRAPHS
    Panda, B. S.
    Pradhan, D.
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2012, 4 (04)
  • [5] On the sets of perfect matchings for two bipartite graphs
    Rosenbloom, A
    INFORMATION PROCESSING LETTERS, 1999, 70 (02) : 95 - 97
  • [6] A decomposition theorem for maximum weight bipartite matchings
    Kao, MY
    Lam, TW
    Sung, WK
    Ting, HF
    SIAM JOURNAL ON COMPUTING, 2001, 31 (01) : 18 - 26
  • [7] Matchings in bipartite graphs with a given number of cuts
    Liu, Jinfeng
    Huang, Fei
    DISCRETE APPLIED MATHEMATICS, 2024, 359 : 303 - 309
  • [8] Semi-matchings for bipartite graphs and load balancing
    Harvey, NJA
    Ladner, RE
    Lovász, L
    Tarnir, T
    JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2006, 59 (01): : 53 - 78
  • [9] Maximum weight induced matching in some subclasses of bipartite graphs
    Panda, B. S.
    Pandey, Arti
    Chaudhary, Juhi
    Dane, Piyush
    Kashyap, Manav
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2020, 40 (03) : 713 - 732
  • [10] Maximum weight induced matching in some subclasses of bipartite graphs
    B. S. Panda
    Arti Pandey
    Juhi Chaudhary
    Piyush Dane
    Manav Kashyap
    Journal of Combinatorial Optimization, 2020, 40 : 713 - 732
12345