New results on induced matchings
作者： Martin Charles Golumbic , Moshe Lewenstein
DOI: 10.1016/S0166-218X(99)00194-8
关键词:
摘要: A matching in a graph is set of edges no two which share common vertex. M an induced if edge connects M. The problem finding maximum known to be NP-Complete general and specifically for bipartite graphs 3-regular planar graphs. has been shown polynomial several classes In this paper we generalize the results wider graphs, improve time complexity previously results.
elsevier.com
sci-hub.se 参考文章(17)
C. W. Ko, F. B. Shepherd, Adding an identity to a totally unimodular matrix Department of Operational Research, London School of Economics and Political Science. ,(1994)
Derek G. Corneil, Stephan Olariu, Lorna Stewart, The ultimate interval graph recognition algorithm symposium on discrete algorithms. pp. 175- 180 ,(1998) , 10.5555/314613.314697
D. T. Lee, M. Sarrafzadeh, Y. F. Wu, Minimum cuts for circular-arc graphs SIAM Journal on Computing. ,vol. 19, pp. 1041- 1050 ,(1990) , 10.1137/0219071
Fănică Gavril, Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph SIAM Journal on Computing. ,vol. 1, pp. 180- 187 ,(1972) , 10.1137/0201013
Martin Charles Golumbic, Renu C. Laskar, Irredundancy in circular arc graphs Discrete Applied Mathematics. ,vol. 44, pp. 79- 89 ,(1993) , 10.1016/0166-218X(93)90223-B
Wen-Lian Hsu, Kuo-Hui Tsai, Linear time algorithms on circular-arc graphs Information Processing Letters. ,vol. 40, pp. 123- 129 ,(1991) , 10.1016/0020-0190(91)90165-E
Martin Charles Golumbic, Comparability graphs and a new matroid Journal of Combinatorial Theory, Series B. ,vol. 22, pp. 68- 90 ,(1977) , 10.1016/0095-8956(77)90049-1
Ido Dagan, Martin Charles Golumbic, Ron Yair Pinter, Trapezoid graphs and their coloring Discrete Applied Mathematics. ,vol. 21, pp. 35- 46 ,(1988) , 10.1016/0166-218X(88)90032-7
Kellogg S. Booth, George S. Lueker, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms Journal of Computer and System Sciences. ,vol. 13, pp. 335- 379 ,(1976) , 10.1016/S0022-0000(76)80045-1
Stefan Felsner, Rudolf Müller, Lorenz Wernisch, Trapezoid graphs and generalizations, geometry and algorithms Discrete Applied Mathematics. ,vol. 74, pp. 13- 32 ,(1997) , 10.1016/S0166-218X(96)00013-3