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. Paper doi abstract bibtex 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}
}
Downloads: 0
{"_id":"q4kcR8Abszd33J9Dk","authorIDs":[],"author_short":["Kashiwabara, T.","Masuda, S.","Nakajima, K.","Fujisawa, T."],"bibbaseid":"kashiwabara-masuda-nakajima-fujisawa-generationofmaximumindependentsetsofabipartitegraphandmaximumcliquesofacirculararcgraph-1992","bibdata":{"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","Masuda, Sumio","Nakajima, Kazuo","Fujisawa, Toshio"],"author_short":["Kashiwabara, T.","Masuda, S.","Nakajima, K.","Fujisawa, T."],"bibtex":"@article{ Kashiwabara1992,\n 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.},\n author = {Kashiwabara, Toshinobu and Masuda, Sumio and Nakajima, Kazuo and Fujisawa, Toshio},\n doi = {10.1016/0196-6774(92)90012-2},\n 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},\n issn = {01966774},\n journal = {Journal of Algorithms},\n month = {March},\n number = {1},\n pages = {161--174},\n title = {{Generation of Maximum Independent Sets of a Bipartite Graph and Maximum Cliques of a Circular-Arc Graph}},\n url = {http://www.sciencedirect.com/science/article/pii/0196677492900122},\n volume = {13},\n year = {1992}\n}","bibtype":"article","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","id":"Kashiwabara1992","issn":"01966774","journal":"Journal of Algorithms","key":"Kashiwabara1992","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","type":"article","url":"http://www.sciencedirect.com/science/article/pii/0196677492900122","volume":"13","year":"1992","bibbaseid":"kashiwabara-masuda-nakajima-fujisawa-generationofmaximumindependentsetsofabipartitegraphandmaximumcliquesofacirculararcgraph-1992","role":"author","urls":{"Paper":"http://www.sciencedirect.com/science/article/pii/0196677492900122"},"downloads":0,"html":""},"bibtype":"article","biburl":"http://www-ikn.ist.hokudai.ac.jp/~wasa/enum.bib","creationDate":"2015-04-23T04:51:45.070Z","downloads":0,"keywords":[],"search_terms":["generation","maximum","independent","sets","bipartite","graph","maximum","cliques","circular","arc","graph","kashiwabara","masuda","nakajima","fujisawa"],"title":"Generation of Maximum Independent Sets of a Bipartite Graph and Maximum Cliques of a Circular-Arc Graph","year":1992,"dataSources":["YRMeqhMHoNu9HzJoC"]}