Michael R. Garey

David S. Johnson

"Shows how to recognize NP-complete problems and offers proactical suggestions for dealing with them effectively. The book covers the basic theory of NP-completeness, provides an overview of alternative directions for further research, and contains and extensive list of NP-complete and NP-hard problems, with more than 300 main entries and several times as many results in total. [This book] is suitable as a supplement to courses in algorithm design, computational complexity, operations research, or combinatorial mathematics, and as a text for seminars on approximation algorithms or computational complexity. It provides not only a valuable source of information for students but also an essential reference work for professionals in computer science"--Back cover.

A Guide to the Theory of NP-completeness

Computers and Intractability

Camil Demetrescu

Andrew V. Goldberg

Ninth DIMACS Implementation Challenge

The Shortest Path Problem

Takao Nishizeki

Akihiro Nozaki

Perspectives in Computing, Volume 15: Discrete Algorithms and Complexity provides an understanding of discrete algorithms and complexity. This book covers a variety of topics, including discrete logarithm algorithms, parallel bubbling, electronic prototyping, number theoretic complexity, and linear programming. Organized into 27 chapters, this volume begins with an overview of the basic solutions of the primal and dual that can be characterized in graph-theoretic terms. This text then explores the principal partition of vertex-weighted graphs, which is utilized to solve certain assignment problems or flow problems that are formulated using such graphs. Other chapters consider a polynomial-time algorithm for finding the geodesic center of a simple polygon. This book discusses as well the three efficient algorithms for the routing problems around a rectangle. The final chapter deals with a snoopy cache multiprocessor system wherein each processor has a cache in which it stores blocks of data. This book is a valuable resource for mathematicians and researchers.

Proceedings of the Japan-US Joint Seminar, June 4 – 6, 1986, Kyoto, Japan

Discrete Algorithms and Complexity

Proceedings of the Japan-US Joint Seminar, June 4-6, 1986, Kyoto, Japan

(preliminary Version)

STOC/FOCS Bibliography

Kathleen Short

Thesia Isedora Garner

1990 to 1997

Experimental Poverty Measures

Michael A. Trick

The purpose of a DIMACS Challenge is to encourage and coordinate research in the experimental analysis of algorithms. The First DIMACS Challenge encouraged experimental work in the area of network flow and matchings. This Second DIMACS Challenge, on which this volume is based, took place in conjunction with the DIMACS Special Year on Combinatorial Optimization. Addressed here are three difficult combinatorial optimization problems: finding cliques in a graph, colouring the vertices of a graph, and solving instances of the satisfiability problem. These problems were chosen both for their practical interest and because of their theoretical intractability.

Second DIMACS Implementation Challenge, October 11-13, 1993

Cliques, Coloring, and Satisfiability

Catherine C. McGeoch

Interest has grown recently in the application of computational and statistical tools to problems in the analysis of algorithms. In many algorithmic domains, worst-case bounds are too pessimistic and tractable probabilistic models too unrealistic to provide meaningful predictions of practical algorithmic performance. Experimental approaches can provide knowledge where purely analytical methods fail and can provide insights to motivate and guide deeper analytical results. The DIMACS Implementation Challenge was organized to encourage experimental work in the area of network flows and matchings. Participants at sites in the U.S., Europe, and Japan undertook projects between November 1990 and August 1991 to test and evaluate algorithms for these problems. The Challenge culminated in a three-day workshop, held in October 1991 at DIMACS. This volume contains the revised and refereed versions of twenty-two of the papers presented at the workshop, along with supplemental material about the Challenge and the Workshop.

First DIMACS Implementation Challenge

Network Flows and Matching

David S. Johnson

About

Books

Join the club