Graph Theory and Integer Programming

DOI10.1016/S0167-5060(08)70822-7zbMath0407.05053MaRDI QIDQ4193501

László Lovász

Publication date: 1979

Published in: Discrete Optimization I, Proceedings of the Advanced Research Institute on Discrete Optimization and Systems Applications of the Systems Science Panel of NATO and of the Discrete Optimization Symposium (Search for Journal in Brave)

zbMATH Keywords

MatchingCutsChromatic NumberMinimax TheoremsInteger ProgrammingGraph TheoryClique Number

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Convex programming (90C25) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Applications of mathematical programming (90C90) Integer programming (90C10) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Coloring of graphs and hypergraphs (05C15) Applications of graph theory to circuits and networks (94C15) Eulerian and Hamiltonian graphs (05C45)

Related Items

Polyhedral proof methods in combinatorial optimization, Relaxations for two-level multi-item lot-sizing problems, Branch and cut algorithms for detecting critical nodes in undirected graphs, Relaxations of Discrete Sets with Semicontinuous Variables, A matching problem with side conditions, Matchings in regular graphs, A compact linear program for testing optimality of perfect matchings., A polyhedral study of lot-sizing with supplier selection, Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover, Valid inequalities for the single arc design problem with set-ups, On the fractional matching polytope of a hypergraph, Semi-continuous network flow problems, Convex hull results for the warehouse problem, Matchings and covers in hypergraphs, Short proofs on the matching polyhedron, Lifting for mixed integer programs with variable upper bounds, The Steiner tree polytope and related polyhedra, Continuous knapsack sets with divisible capacities