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.

Report Date:

1983-11-01

Pagination or Media Count:

18.0

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