Generation of Maximum Independent Sets of a Bipartite Graph and Maximum Cliques of a Circular-Arc Graph. Kashiwabara, T., Masuda, S., Nakajima, K., & Fujisawa, T. Journal of Algorithms, 13(1):161--174, March, 1992.
We present an efficient algorithm for generating all maximum independent sets of a bipartite graph. Its time complexity is O(n2.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(n3.5 + (output size)) time.
@article{ Kashiwabara1992,
abstract = {We present an efficient algorithm for generating all maximum independent sets of a bipartite graph. Its time complexity is O(n2.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(n3.5 + (output size)) time.},
author = {Kashiwabara, Toshinobu and Masuda, Sumio and Nakajima, Kazuo and Fujisawa, Toshio},
doi = {10.1016/0196-6774(92)90012-2},
file = {:Users/KunihiroWASA/Dropbox/paper/1992/Kashiwabara et al., Generation of Maximum Independent Sets of a Bipartite Graph and Maximum Cliques of a Circular-Arc Graph, 1992.pdf:pdf},
issn = {01966774},
journal = {Journal of Algorithms},
month = {March},
number = {1},
pages = {161--174},
title = {{Generation of Maximum Independent Sets of a Bipartite Graph and Maximum Cliques of a Circular-Arc Graph}},
url = {http://www.sciencedirect.com/science/article/pii/0196677492900122},
volume = {13},
year = {1992}
}