New results on induced matchings

被引：97

作者：

Golumbic, MC ^{[1
]}

Lewenstein, M ^{[1
]}

机构：

[1] Bar Ilan Univ, Dept Math & Comp Sci, IL-52900 Ramat Gan, Israel

来源：

DISCRETE APPLIED MATHEMATICS | 2000年 / 101卷 / 1-3期

关键词：

graph theory; perfect graphs; design and analysis of algorithms; matchings; induced matchings; strong matchings;

D O I：

10.1016/S0166-218X(99)00194-8

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A matching in a graph is a set of edges no two of which share a common vertex. A matching M is an induced matching if no edge connects two edges of M. The problem of finding a maximum induced matching is known to be NP-Complete in general-and specifically for bipartite graphs and for 3-regular planar graphs. The problem has been shown to be polynomial for several classes of graphs. In this paper we generalize the results to:wider classes of graphs, and improve the time complexity of previously known results. (C) 2000 Elsevier Science B.V. All rights reserved.

引用

页码：157 / 165

页数：9

共 17 条

[1] TESTING FOR CONSECUTIVE ONES PROPERTY, INTERVAL GRAPHS, AND GRAPH PLANARITY USING PQ-TREE ALGORITHMS [J].

BOOTH, KS ;

LUEKER, GS .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1976, 13 (03) :335-379

[2] INDUCED MATCHINGS [J].

CAMERON, K .

DISCRETE APPLIED MATHEMATICS, 1989, 24 (1-3) :97-102

[3]

Corneil D.G., 1998, Symposium on Discrete Algorithms, P175

[4] TRAPEZOID GRAPHS AND THEIR COLORING [J].

DAGAN, I ;

GOLUMBIC, MC ;

PINTER, RY .

DISCRETE APPLIED MATHEMATICS, 1988, 21 (01) :35-46

[5] Trapezoid graphs and generalizations, geometry and algorithms [J].

Felsner, S ;

Muller, R ;

Wernisch, L .

DISCRETE APPLIED MATHEMATICS, 1997, 74 (01) :13-32

[6]

Fricke G., 1992, C NUMER, V89, P239

[7]

Gavril F., 1972, SIAM Journal on Computing, V1, P180, DOI 10.1137/0201013

[8] CHARACTERIZATION OF COMPARABILITY GRAPHS + OF INTERVAL GRAPHS [J].

GILMORE, PC ;

HOFFMAN, AJ .

CANADIAN JOURNAL OF MATHEMATICS, 1964, 16 (03) :539-&

[9] STABILITY IN CIRCULAR ARC GRAPHS [J].

GOLUMBIC, MC ;

HAMMER, PL .

JOURNAL OF ALGORITHMS, 1988, 9 (03) :314-320

[10] COMPARABILITY GRAPHS AND A NEW MATROID [J].

GOLUMBIC, MC .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1977, 22 (01) :68-90

← 1 2 →