The Perfectly Matchable Subgraph Polytope of an Arbitrary Graph.

Abstract

The Perfectly Matchable Subgraph Polytope of a graph G=(V,E), denoted by PMS (G) is the convex hull of the incidence vectors of those X is a subset of V which induce a subgraph having a perfect matching. A linear system is described, whose solution set is PMS (G), for a general (nonbipartite) graph G. It can be derived via a projection technique from Edmonds' characterization of the matching polytope of G. This system can be deduced from the earlier bipartite case, by using the Edmonds- Gallai structure theorem. Finally, we characterize which inequalities are facet inducing for PMS (G), and hence essential. Keywords Projection; Perfectly Matchable Subgraph Polytype; Polyhedral Combinatorics; Matching Theory.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1987
Accession Number
ADA185993

Entities

People

  • Egon Balas
  • William R. Pulleyblank

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Engineering
  • Equations
  • Generators
  • Inequalities
  • Linear Programming
  • Linear Systems
  • Mathematics
  • Military Research
  • Operations Research
  • Optimization
  • Students
  • Two Dimensional

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.