An extension of matching theory |
| |
Authors: | Grard Cornujols David Hartvigsen |
| |
Institution: | Gérard Cornuéjols,David Hartvigsen |
| |
Abstract: | Given a graph G and a family H of hypomatchable subgraphs of G, we introduce the notion of a hypomatching of G relative to H as a collection of node disjoint edges and subgraphs, where the subgraphs all belong to H. Examples include matchings (H = Ø), fractional matchings (H contains all the hypomatchable subgraphs of G), and edge-and-triangle packings (H is the set of 3-cliques of G). We show that many of the classical theorems about maximum cardinality matchings can be extended to hypomatchings which cover the maximum number of nodes in a graph. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|