Progress in Combinatorial Optimization - 1st Edition - ISBN: 9780125667807, 9781483264530

Progress in Combinatorial Optimization

1st Edition

Editors: 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
15% off
15% off
15% off
Price includes VAT/GST
× DRM-Free

Easy - Download and start reading immediately. There’s no activation process to access eBooks; all eBooks are fully searchable, and enabled for copying, pasting, and printing.

Flexible - Read on multiple operating systems and devices. Easily read eBooks on smart phones, computers, or any eBook readers, including Kindle.

Open - Buy once, receive and download all available eBook formats, including PDF, EPUB, and Mobi (for Kindle).

Institutional Access

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
Academic Press
eBook ISBN:

About the Editor

William R. Pulleyblank

Ratings and Reviews