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) : Balas,Egon

Report Date : FEB 1987

Pagination or Media Count : 13

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.

Descriptors :   *GRAPHS, CYCLES, DECOMPOSITION, MATCHING

Subject Categories : Numerical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE