ISSN:
1436-4646
Keywords:
Polyhedral Combinatorics
;
Combinatorial Optimization
;
Total Dual Integrality
;
Connected Subgraphs
;
Optimal Subtrees
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract Given a graphG = (V, E), leta S, S ∈ L, be the edge set incidence vectors of its nontrivial connected subgraphs. The extreme points ofℬ = {x ∈ R E: asx ≤ |V(S)| - |S|, S ∈ L} are shown to be integer 0/± 1 and characterized. They are the alternating vectorsb k, k ∈ K, ofG. WhenG is a tree, the extreme points ofB ≥ 0,b kx ≤ 1,k ∈ K} are shown to be the connected vectors ofG together with the origin. For the four LP's associated withℬ andA, good algorithms are given and total dual integrality ofℬ andA proven.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01589348
Permalink