The Assignable Subgraph Polytope of a Directed Graph.
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1987
- Accession Number
- ADA180860
Entities
People
- Egon Balas
Organizations
- Carnegie Mellon University