INDUCED MATCHINGS
INDUCED MATCHINGS
复制标题
DOI：
10.1016/0166-218x(92)90275-f
复制
发表时间：
1989-08-01
影响因子：
1.1
通讯作者：
CAMERON, K
中科院分区：
文献类型：
--
作者：
CAMERON, K
图G中的诱导匹配是一组边，其中没有两条边与G的公共节点相交或由G的边连接;也就是说，诱导匹配是形成诱导子图的匹配。我们发现，问题找到一个最大的诱导匹配是NP-完全的二部图。另一方面，在弦图中，最大诱导匹配很容易找到和识别，并且可以并行快速找到。
Aninduced matchingin a graphGis a set of edges, no two of which meet a common node or are joined by an edge ofG; that is, an induced matching is a matching which forms an induced subgraph. We show that the problem of finding a largest induced matching is NP-complete for bipartite graphs. On the other hand, in chordal graphs, a largest induced matching is easy to find and to recognize, and can be found fast in parallel.