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

Simple item page
dc.contributor.authorKashiwabara, Toshinobuen_US
dc.contributor.authorMasuda, Sumioen_US
dc.contributor.authorNakajima, K.en_US
dc.contributor.authorFujisawa, Toshioen_US
dc.contributor.departmentISRen_US
dc.date.accessioned2007-05-23T09:43:59Z
dc.date.available2007-05-23T09:43:59Z
dc.date.issued1989en_US
dc.description.abstractWe 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.en_US
dc.format.extent669978 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/1903/4905
dc.language.isoen_USen_US
dc.relation.ispartofseriesISR; TR 1989-65en_US
dc.titleGeneration of Maximum Independent Sets of a Biparite Graph and Maximum Cliques of a Circular-Arc Graph.en_US
dc.typeTechnical Reporten_US

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
TR_89-65.pdf
Size:
654.28 KB
Format:
Adobe Portable Document Format
Download

Collections

Institute for Systems Research Technical Reports