Progress in Combinatorial OptimizationWilliam R. Pulleyblank |
From inside the book
Results 1-3 of 57
Page 110
... polynomial time . Thus , comparability graphs and line - graphs of bipartite graphs might play the role of primitive ... polynomial - time algorithm for recognizing perfect graphs , one would have to ( a * ) recognize the primitive ...
... polynomial time . Thus , comparability graphs and line - graphs of bipartite graphs might play the role of primitive ... polynomial - time algorithm for recognizing perfect graphs , one would have to ( a * ) recognize the primitive ...
Page 124
... polynomial - time algorithm for solving ( 3.3 ) , but the polynomial - time bound is based on having an initial feasible solution to ( 3.3 ) and a polynomial - time algorithm for minimiz- ing a submodular function . Subsequent to this ...
... polynomial - time algorithm for solving ( 3.3 ) , but the polynomial - time bound is based on having an initial feasible solution to ( 3.3 ) and a polynomial - time algorithm for minimiz- ing a submodular function . Subsequent to this ...
Page 175
... polynomial time a reduced basis of the lattice L ( a1 , ... , an ) . The algorithm in Theorem 2.10 is quite straightforward from the definition of reducedness : if ( a ) is violated the subtract ( μ ) b , from b ( where ( u ) is the ...
... polynomial time a reduced basis of the lattice L ( a1 , ... , an ) . The algorithm in Theorem 2.10 is quite straightforward from the definition of reducedness : if ( a ) is violated the subtract ( μ ) b , from b ( where ( u ) is the ...
Contents
Lifting the Facets of Polyhedra | 3 |
Partitioning Spectra and Linear Programming 113 | 13 |
Oriented Matroids and Triangulations of Convex Polytopes 22 | 27 |
Copyright | |
16 other sections not shown
Other editions - View all
Common terms and phrases
adjacent apply arcs arrow B₁ basic Meyniel graph bipartite graph bisimplicial box totally dual C₁ chain circuit clique cocircuit columns combinatorial optimization Computer connected components contains convex corresponding crossing family decomposition defined denote digraph directed graph disjoint dynamic graph edges Edmonds element ellipsoid method equivalent eulerian path exists facet feasible G(V₁ G₁ G₂ given graph G greedoid greedy algorithm Hence implies induced induced subgraph inequalities intersecting interval order K₁ lattice LEMMA Let G linear program linear system Lovász machines matching Math Mathematical matrix maximal maximum minimal network flow node NP-complete obtain oriented matroid pairs partial order partially ordered set partition path perfect graphs points polyhedra polyhedron polymatroid polynomial polytope proof result satisfies schedule Schrijver solve structure subgraph submodular function subsets supermodular theorem theory tion total dual integrality U₁ V₁ vector vertex vertices x₁ y₁