# Search

Now showing items 1-10 of 13

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

#### System Level Fault Diagnosis: An Overview.

(1986)

Recent times have seen a rapid growth in the development of digital systems. The cost of the hardware has shown a remarkable decline allowing designers to build systems which are extremely complex. This in turn has resulted ...

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

#### A Note on the NP-hardness of the Topological Via Minimization Problem.

(1989)

Suppose that we are given a two-layer routing area bounded by a closed continuous curve B, a set of terminals placed on B which are available on both layers, and a set of two terminal-nets. The topological via minimization ...

#### Complexity Results for Rectangle Intersection and Overlap Graphs.

(1988)

Let R be a family of iso-oriented rectangles in the plane. A graph G = (V, E) is called a rectangle intersection (resp., overlap) graph for R if there is a one-to-one correspondence between V and R such that two vertices ...

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