An historical overview of computational complexity is presented. Emphasis is on the
fundamental issues of defining the intrinsic computational complexity of a problem and …

Algorithms and data structures developed to solve graph problems on parallel computers
are surveyed. The problems discussed relate to searching graphs and finding connected …

This database theory book provides a focused presentation of the core material on relational
databases, and presents a number of advanced topics in a unified framework. Some of the …

Alternation is a generalization of nondeterminism in which existential and universal
quantitiers can alternate during the course of a computation, whereas in a nondeterministic …

Any n-vertex planar graph has the property that it can be divided into components of roughly
equal size by removing only O (√ n) vertices. This separator theorem, in combination with a …

This book provides a comprehensive analysis of the most important topics in parallel
computation. It is written so that it may be used as a self-study guide to the field, and …

The birth of the theory of computational complexity can be set in the early 1960s when the
first users of electronic computers started to pay increasing attention to the performances of …

This handbook provides an up-to-date compendium of fundamental computer science
topics, techniques, and applications. Along with updating and revising many of the existing …

This is the second volume of a two volume collection on Structural Complexity. This volume
assumes as a prerequisite knowledge about the topics treated in Volume I, but the present …

This paper concerns the computational complexity of depth-first search. Suppose we are
given a rooted graph G with fixed adjacency lists and vertices u, v. We wish to test if u is first …