Degree Constrained Subgraphs of Linear Graphs |
Common terms and phrases
Algorithm Figure alternating path alternating tree augmenting path bipartite graph cardinality algorithm cardinality UDCS Chapter circuit component d-factor degree constrained subgraph degree constraints dual linear programs edge eij edge weights Edmonds expanded exposed vertex feasible primal feasible solution graph G growth Hungarian tree incidence matrix inner vertex integer program matching problem max cx subject maximum cardinality solution maximum matching maximum solution MDCS minimum nonorthogonal number of edges number of vertices odd cycles orthogonality conditions outer vertex outermost blossom polyhedron primal and dual Proof S-odd subgraph satisfy saturated set of edges set of vertices shown simplex algorithm solution to Ax solved strong augment symmetric difference Theorem TRANSFER tree is discarded Tutte UDCS blossoms UDCS cardinality UDCS problem UDCS solution ULDCS unsaturated unscanned V₁ vector vertex V1 W. T. Tutte Weak augment weighted graph weighted UDCS algorithm y₁