An Extension of Matching Theory.

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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1983
Accession Number
ADA137605

Entities

People

  • D. Hartvigsen
  • G. Cornuejols

Organizations

  • Carnegie Mellon University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Boundaries
  • Construction
  • Contracts
  • Coverings
  • Decomposition
  • Governments
  • Iterations
  • Literature
  • Mathematics
  • Military Research
  • Observation
  • Schools
  • Sequences
  • Triangles
  • Universities

Readers

  • Graph Algorithms and Convex Optimization.