Data Structures and Algorithms 2

In this chapter we treat efficient algorithms for many basic problems on graphs: topological sorting and transitive closure, connectivity and biconnectivity, least cost paths, least cost spanning trees, network flow problems and matching problems and planarity testing.

The CLIQUE problem is as follows: Input is an undirected graph G = (V,E) with n nodes and an integer k. The question is to decide whether the complete graph on k nodes is a subgraph of G, i.e. whether there is V′ ⊆ V, │V′│ = k such that (u,v) ∈ E for all u,v ∈ V′. There is a trivial, but inefficient algorithm to solve the CLIQUE problem. Run through all subsets V′ ⊆ V of cardinality k and check whether V′ induces a complete graph. There are \(\left( {\begin{array}{*{20}{c}} n \\ k \\ \end{array} } \right)\) sets V′ with k elements. Thus our simple algorithm checks \(\left( {\begin{array}{*{20}{c}} n \\ {n/2} \\ \end{array} } \right) \geqslant {2^n}/\left( {n + 1} \right)\) ≥ 2ⁿ/(n+1) subsets in the case k = n/2. It is simple to check a subset V′ for the clique property; time n will certainly suffice, and one time unit is certainly required. We conclude that our naive algorithm has running time at least 2ⁿ/(n+1). Before we can state that this is inefficient, we have to define problem size. We assume throughout this chapter, that combinatorial objects, i.e. graphs, integers, sets,…, are coded over a finite alphabet in some “natural way”. More precisely, we assume that graphs are coded by their adjacency matrix, i.e. a graph G with n nodes is coded by a bitstring of length n², the entries of the matrix in row major order. Integers are always written in binary and sets are specified by listing their elements in some order. In this way a problem instance of the clique problem is a bistring of length n² + log(n/2) + 1, again assuming k = n/2 for simplicity.

There are basically two ways for structuring a book on data structures and algorithms: problem or paradigm oriented. We have mostly followed the first alternative because it allows for a more concise treatment. However, at certain occassions (e.g. section VIII.4 on the sweep paradigm in computational geometry) we have also followed the second approach. In this last chapter of the book we attempt to review the entire book from the paradigm oriented point of view.