On maximum induced matchings in bipartite graphs

被引：68
作者：
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 条
[21]   Bipartite Graphs with the Maximum Sum of Squares of Degrees [J].
Sheng-gui ZHANG ;
Chun-cao ZHOU .
Acta Mathematicae Applicatae Sinica, 2014, (03) :801-806
[22]   PERFECT MATCHINGS IN O(n log n) TIME IN REGULAR BIPARTITE GRAPHS [J].
Goel, Ashish ;
Kapralov, Michael ;
Khanna, Sanjeev .
SIAM JOURNAL ON COMPUTING, 2013, 42 (03) :1392-1404
[23]   Perfect Matchings in O(n log n) Time in Regular Bipartite Graphs [J].
Goel, Ashish ;
Kapralov, Michael ;
Khanna, Sanjeev .
STOC 2010: PROCEEDINGS OF THE 2010 ACM SYMPOSIUM ON THEORY OF COMPUTING, 2010, :39-46
[24]   MAXIMUM CARDINALITY SIMPLE 2-MATCHINGS IN SUBCUBIC GRAPHS [J].
Hartvigsen, David ;
Li, Yanjun .
SIAM JOURNAL ON OPTIMIZATION, 2011, 21 (03) :1027-1045
[25]   Partitioning to three matchings of given size is NP-complete for bipartite graphs [J].
Palvolgyi, Domotor .
ACTA UNIVERSITATIS SAPIENTIAE INFORMATICA, 2014, 6 (02) :206-209
[26]   Parallel maximum independent set in convex bipartite graphs [J].
Czumaj, A ;
Diks, K ;
Przytycka, TM .
INFORMATION PROCESSING LETTERS, 1996, 59 (06) :289-294
[27]   Identifying codes in bipartite graphs of given maximum degree [J].
Chakraborty, Dipayan ;
Foucaud, Florent ;
Lehtila, Tuomo .
XII LATIN-AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, LAGOS 2023, 2023, 224 :157-165
[28]   Bounds on maximum concurrent flow in random bipartite graphs [J].
Fernando E. Vilas ;
Eli V. Olinick ;
David W. Matula .
Optimization Letters, 2020, 14 :2197-2209
[29]   MAXIMUM SEMI-MATCHING PROBLEM IN BIPARTITE GRAPHS [J].
Katrenic, Jan ;
Semanisin, Gabriel .
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2013, 33 (03) :559-569
[30]   Bounds on maximum concurrent flow in random bipartite graphs [J].
Vilas, Fernando E. ;
Olinick, Eli V. ;
Matula, David W. .
OPTIMIZATION LETTERS, 2020, 14 (08) :2197-2209
12345