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.
Descriptors:
Subject Categories:
- Numerical Mathematics