COVID-19 Update: We are currently shipping orders daily. However, due to transit disruptions in some geographies, deliveries may be delayed. To provide all customers with timely access to content, we are offering 50% off Science and Technology Print & eBook bundle options. Terms & conditions.
Progress in Combinatorial Optimization - 1st Edition - ISBN: 9780125667807, 9781483264530

Progress in Combinatorial Optimization

1st Edition

Editor: William R. Pulleyblank
eBook ISBN: 9781483264530
Imprint: Academic Press
Published Date: 28th January 1984
Page Count: 386
Sales tax will be calculated at check-out Price includes VAT/GST
Price includes VAT/GST

Institutional Subscription

Secure Checkout

Personal information is secured with SSL technology.

Free Shipping

Free global shipping
No minimum order.


Progress in Combinatorial Optimization provides information pertinent to the fundamental aspects of combinatorial optimization. This book discusses how to determine whether or not a particular structure exists.

Organized into 21 chapters, this book begins with an overview of a polar characterization of facets of polyhedra obtained by lifting facets of lower dimensional polyhedra. This text then discusses how to obtain bounds on the value of the objective in a graph partitioning problem in terms of spectral information about the graph. Other chapters consider the notion of a triangulation of an oriented matroid and show that oriented matroid triangulation yield triangulations of the underlying polytopes. This book discusses as well the selected results and problems on perfect ad imperfect graphs. The final chapter deals with the weighted parity problem for gammoids, which can be reduced to the weighted graphic matching problem.

This book is a valuable resource for mathematicians and research workers.

Table of Contents




Lifting the Facets of Polyhedra

Partitioning, Spectra and Linear Programming

Oriented Matroids and Triangulations of Convex Polytopes

Recent Algorithms for Two Versions of Graph Realization and Remarks on Applications to Linear Programming

Polynomial Algorithm to Recognize a Meyniel Graph

Integer Programming Problems for Which a Simple Rounding-Type Algorithm Works

Notes on Perfect Graphs

Total Dual Integrality of Linear Inequality Systems

Numbers of Lengths for Representations of Interval Orders

Submodular Rows

Geometric Methods in Combinatorial Optimization

A Fast Algorithm That Makes Matrices Optimally Sparse

Structural Theory for the Combinatorial Systems Characterized by Submodular Functions

Greedoids—A Structural Framework for the Greedy Algorithim

Preemptive Scheduling of Uniform Machines Subject to Release Dates

An Application of Matroid Polyhedral Theory to Unit-Execution Time, Tree-Precedence Job Scheduling

Some Problems on Dynamic/Periodic Graphs

Polytopes and Complexity

Statics and Electric Network Theory: A Unifying Role of Matroids

Total Dual Integrality from Directed Graphs, Crossing Families, and Sub- and Supermodular Functions

Solving the Weighted Parity Problem for Gammoids by Reduction to Graphic Matching


No. of pages:
© Academic Press 1984
28th January 1984
Academic Press
eBook ISBN:

About the Editor

William R. Pulleyblank

Ratings and Reviews