Accession Number : ADA137605

Title :   An Extension of Matching Theory.

Descriptive Note : Management sciences research rept.,

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s) : Cornuejols,G ; Hartvigsen,D

PDF Url : ADA137605

Report Date : Nov 1983

Pagination or Media Count : 18

Abstract : The authors introduce the notion of a hypomatching in a graph G as a collection of node disjoint edges and hypomatchable subgraphs of G where the hypomatchable subgraphs belong to some prespecified family. Examples include matchings, fractional matchings and edge-and-triangle packings. It is shown 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. (Author)

Descriptors :   *Matching, *Theory, *Graphs, Theorems, Nodes, Set theory, Algorithms

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE