Graph theory and combinatorial optimization

David Avis, Alain Hertz, Odile Marcotte0387255915, 9780387255927, 9780387255910, 0387255923

Graph theory is very much tied to the geometric properties of optimization and combinatorial optimization. Moreover, graph theory’s geometric properties are at the core of many research interests in operations research and applied mathematics. Its techniques have been used in solving many classical problems including maximum flow problems, independent set problems, and the traveling salesman problem.

GRAPH THEORY AND COMBINATORIAL OPTIMIZATION explores the field’s classical foundations and its developing theories, ideas and applications to new problems. Belhaiza et al (Chapter 1) study several conjectures on the algebraic connecticity of graphs. Brass and Pach (Chapter 2) survey the results in the theory of geometric patterns. Fukuda and Rosta (Chapter 3) discuss various data depth measures that were first introduced in nonparametric statistics. Hertz and Lozin (Chapter 4) examine the method of augmenting graphs for solving the maximum independent set problem. Krishnan and Terlaky (Chapter 5) present a survey of semidefinite and interior point methods for solving NP-hard combinatorial optimization problems to optimality and designing approximation algorithms for some of these problems. Kubiak (Chapter 6) presents a study of balancing mixed-model supply chains. Marcotte and Savard (chapter 7) outline and overview two classes of bilevel programs. Shepherd and Vetta (Chapter 8) present a study of disjoins, and de Werra (Chapter 9) generalizes a coloring property of unimodular hypergraphs.

The book examines the geometric properties of graph theory and its widening uses in combinatorial optimization theory and application. The field’s leading researchers have contributed chapters in their areas of expertise.