# Search

Now showing items 1-10 of 10

#### Efficient Enumeration of Maximal and Maximum Independent Sets of an Interval Graph and a Circular-Arc Graph.

(1987)

We present efficient algorithms for generating all maximal and all maximum independent sets of an interval graph and a circular- arc graph. When an interval graph is given in the form of a family of n intervals, the first ...

#### A Linear Time Algorithm for Circular Permutation Layout.

(1988)

Suppose that two sets of terminals t_l,t_2,...,t_n and b_1,b_2,...,b_n are located on two concentric circles C_out and C_in, respectively. Given a permutation PI of integers 1,2,...,n, the circular permutation layout problem ...

#### Circular Permutation Layout with Prescribed Between-Pin Congestions.

(1989)

Suppose that two sets of terminals t_1,t_2, ..., t_n and b_1, b_2, ... ,b_n are located on two concentric circles C_out and C_in, respectively. Given a permutation PI of integers 1, 2, ..., n, the circular permutation ...

#### Generation of Maximum Independent Sets of a Biparite Graph and Maximum Cliques of a Circular-Arc Graph.

(1989)

We present an efflcient algorithm for generating all maximum independent sets of a bipartite graph. Its time complexity is O (n sup 2.5 + (output size )), where n is the number of vertices of a given graph. As its application, ...

#### Crossing Minimization in the Straight-Line Embedding of Graphs.

(1987)

The problem of embedding a graph in the plane with the minimum number of edgecrossings arises in some circuit layout problems. It has been known that this problem is in general NP-hard. An interesting and relevant problem ...

#### The Via Minimization Problem is NP-Complete.

(1987)

Vias between different layers of interconnection on dense integrated circuits tend to reduce yield, degrade performance, and take up a large amount of chip area. Similarly, contact holes on multilayer printed circuit boards ...

#### 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, ...

#### Circular-Arc Containment Graphs.

(1988)

We introduce a new class of containment graphs called circular- arc containment graphs. A graph is called a circular-arc containment graph if there exists a family of arcs on a circle, such that each vertex corresponds to ...