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)

← 1 2 3 →