An o*(1.4786n)-time algorithm for the maximum induced matching problem

被引:0
作者
机构
[1] Department of Computer Science and Information Engineering, HungKuang University, 43302 Sha Lu, Taichung
[2] Department of Computer Science and Information Engineering, National Chung Cheng University, 62102 Min-Hsiung, Chiayi
来源
| 1600年 / Springer Science and Business Media Deutschland GmbH卷 / 20期
关键词
D O I
10.1007/978-3-642-35452-6_7
中图分类号
学科分类号
摘要
Given a graph G = (V,E) the MAXIMUM r-REGULAR INDUCED SUBGRAPH problem is to find a vertex set R ⊆ V of maximum cardinality such that G[R] is r-regular. An induced matching M ⊆ E in a graph G = (V,E) is a matching such that no two edges in M are joined by any third edge of the graph. The MAXIMUM INDUCED MATCHING problem is to find an induced matching of maximum cardinality. By definition the maximum induced matching problem is the maximum 1-regular induced subgraph problem. Gupta et al. gave an o(2n) time algorithm for solving the MAXIMUM r-REGULAR INDUCED SUBGRAPH problem. This algorithm solves the MAXIMUM INDUCED MATCHING problem in time O * (1.6957n) where n is the number of vertices in the input graph. In this paper, we show that the maximum induced matching problem can be reduced to the maximum independent set problem and we give a more efficient algorithm for the MAXIMUM INDUCED MATCHING problem running in time O * (1.4786n). © Springer-Verlag Berlin Heidelberg 2013.
引用
收藏
页码:49 / 58
页数:9
相关论文
共 21 条
[1]  
Binkele-Raible D., Brankovic L., Cygan M., Fernau H., Kneis J., Kratsch D., Langer A., Liedloff M., Pilipczuk M., Rossmanith P., Wojtaszczyk J.O., Breaking the 2n-barrier for irredundance: Two lines of attack, Journal of Discrete Algorithms, 9, pp. 214-230, (2011)
[2]  
Cardoso D.M., Kaminski M., Lozin V., Maximum k-Regular Induced Subgraphs, Rutcor Research Report (RRR), (2006)
[3]  
Cameron K., Induced matching, Discrete Applied Mathematics, 24, pp. 97-102, (1989)
[4]  
Cameron K., Sritharan R., Tang Y., Finding a maximum induced matching in weakly chordal graphs, Discrete Mathematics, 266, pp. 133-142, (2003)
[5]  
Duckworth W., Manlove D.F., Zito M., On the approximability of the maximum induced matching problem, Journal of Discrete Algorithms, 3, pp. 79-91, (2005)
[6]  
Erman R., Kowalik L., Krnc M., Walen T., Improved induced matching in sparse graphs, Discrete Applied Mathematics, 158, pp. 1994-2003, (2010)
[7]  
Fomin F.V., Kratsch D., Exact Exponential Algorithms, (2010)
[8]  
Fricke G., Laskar R., String matching in trees, Congressum Numeratium, 89, pp. 239-243, (1992)
[9]  
Gupta S., Raman V., Saurabh S., Fast Exponential Algorithms for Maximum r-Regular Induced Subgraph Problems, FSTTCS 2006. LNCS, 4337, pp. 139-151, (2006)
[10]  
Hosono K., Induced forests in trees and outerplanar graphs, Proceedings of the Faculty of Science of Tokai University, 25, pp. 27-29, (1990)