Accession Number:

ADA180860

Title:

The Assignable Subgraph Polytope of a Directed Graph.

Descriptive Note:

Management science research rept.,

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s):

Report Date:

1987-02-01

Pagination or Media Count:

13.0

Abstract:

Given a directed graph, its assignable subgraph polytope is the convex hull of incidence vectors of subgraphs that have an assignment. Based on earlier results of Balas and Pulleyblank, given a linear characterization of the assignable subgraph polytope of an arbitrary digraph. As a byproduct, the author also characterizes the s-t path decomposable subgraph polytope of an acyclic digraph. Keywords Assignment Cycle decomposition Path decomposition Matching.

Subject Categories:

  • Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE