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

Loading...
Thumbnail Image

Files

TR_89-65.pdf (654.28 KB)
No. of downloads: 778

Publication or External Link

Date

1989

Advisor

Citation

DRUM DOI

Abstract

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, we develop an algorithm for generating all maximum cliques of a circular-arc graph. When the graph is given in the form of a family of n arcs on a circle, this algorithm runs in O ( n sup 3.5 + (output size )) time.

Notes

Rights