# Search

Now showing items 1-3 of 3

#### Efficient Algorithms for Finding Maximum Cliques of an Overlap Graph.

(1986)

Let F = {I_1, I_2, ..., I_n} be a finite family of closed intervals on the real line. For two distinct intervals I_j and I_k in F, we say that I_j and I_k overlap with each other if they interact with each other but neither ...

#### An NP-Hard Crossing Minimization Problem for Computer Network Layout.

(1986)

A layout problem of computer communication network is formulated graph-theoretically as follows: "Given a simple graph G = (V,E), find an embedding of G with the minimum number of edge-crossings such that (i) the vertices ...

#### An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph.

(1986)

A new algorithm is presented for finding a maximum independent set of a circular-arc graph. When the graph is given in the form of a family of n arcs, our algorithm requires only O(n log n) time and O(n) space. Furthermore, ...