Connected and alternating vectors: Polyhedra and algorithms

Abstract

Given a graph G = (V, E), let aS, S ∈ L, be the edge set incidence vectors of its nontrivial connected subgraphs. The extreme points of ℬ = {x ∈ RE: asx ≤ |V(S)| - |S|, S ∈ L} are shown to be integer 0/± 1 and characterized. They are the alternating vectors bk, k ∈ K, of G. When G is a tree, the extreme points of B ≥ 0, bkx ≤ 1, k ∈ K} are shown to be the connected vectors of G together with the origin. For the four LP's associated with ℬ and A, good algorithms are given and total dual integrality of ℬ and A proven. © 1981 North-Holland Publishing Company.