Connected and alternating vectors: Polyhedra and algorithms |
| |
Authors: | Heinz Gröflin Thomas M Liebling |
| |
Institution: | (1) IBM T.J. Watson Research Center, 10598 Yorktown Heights, NY, USA;(2) Swiss Federal Institute of Technology, Zurich, Switzerland |
| |
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.On leave from Swiss Federal Institute of Technology, Zurich. |
| |
Keywords: | Polyhedral Combinatorics Combinatorial Optimization Total Dual Integrality Connected Subgraphs Optimal Subtrees |
本文献已被 SpringerLink 等数据库收录! |
|