A New Algorithm for Generating All the Maximal Independent Sets. Tsukiyama, S., Ide, M., Ariyoshi, H., & Shirakawa, I. SIAM Journal on Computing, 6(3):505--517, September, 1977.
Paper doi abstract bibtex Theproblem of generating all the maximal independent sets (or maximalcliques) of a given graph is fundamental in graph theoryand is also one of the most important in termsof the application of graph theory. In this paper, wepresent a new efficient algorithm for generating all the maximalindependent sets, for which processing time and memory space arebounded by O(nmmu) and O(n+m), respectively, where n, m, andmu are the numbers of vertices, edges, and maximal independentsets of a graph. 1977 (Copyright) Society for Industrial and Applied Mathematics
@article{ Tsukiyama1977a,
abstract = {Theproblem of generating all the maximal independent sets (or maximalcliques) of a given graph is fundamental in graph theoryand is also one of the most important in termsof the application of graph theory. In this paper, wepresent a new efficient algorithm for generating all the maximalindependent sets, for which processing time and memory space arebounded by O(nmmu) and O(n+m), respectively, where n, m, andmu are the numbers of vertices, edges, and maximal independentsets of a graph. 1977 (Copyright) Society for Industrial and Applied Mathematics},
author = {Tsukiyama, Shuji and Ide, Mikio and Ariyoshi, Hiromu and Shirakawa, Isao},
doi = {10.1137/0206036},
file = {:Users/KunihiroWASA/Dropbox/paper/1977/Tsukiyama et al., A New Algorithm for Generating All the Maximal Independent Sets, 1977.pdf:pdf},
issn = {0097-5397},
journal = {SIAM Journal on Computing},
keywords = {1,4,6,algorithm,all the maximal independent,and is also interesting,backtracking,graph,in terms of complexity,introduction,is fundamental in the,its applications,maximal clique,maximal cliques,maximal independent set,of computation,or,sets,the efficient search for,theory of graphs and},
month = {September},
number = {3},
pages = {505--517},
title = {{A New Algorithm for Generating All the Maximal Independent Sets}},
url = {http://epubs.siam.org/doi/abs/10.1137/0206036},
volume = {6},
year = {1977}
}
Downloads: 0
{"_id":"xccyhFBHBAbYn6oGf","authorIDs":[],"author_short":["Tsukiyama, S.","Ide, M.","Ariyoshi, H.","Shirakawa, I."],"bibbaseid":"tsukiyama-ide-ariyoshi-shirakawa-anewalgorithmforgeneratingallthemaximalindependentsets-1977","bibdata":{"abstract":"Theproblem of generating all the maximal independent sets (or maximalcliques) of a given graph is fundamental in graph theoryand is also one of the most important in termsof the application of graph theory. In this paper, wepresent a new efficient algorithm for generating all the maximalindependent sets, for which processing time and memory space arebounded by O(nmmu) and O(n+m), respectively, where n, m, andmu are the numbers of vertices, edges, and maximal independentsets of a graph. 1977 (Copyright) Society for Industrial and Applied Mathematics","author":["Tsukiyama, Shuji","Ide, Mikio","Ariyoshi, Hiromu","Shirakawa, Isao"],"author_short":["Tsukiyama, S.","Ide, M.","Ariyoshi, H.","Shirakawa, I."],"bibtex":"@article{ Tsukiyama1977a,\n abstract = {Theproblem of generating all the maximal independent sets (or maximalcliques) of a given graph is fundamental in graph theoryand is also one of the most important in termsof the application of graph theory. In this paper, wepresent a new efficient algorithm for generating all the maximalindependent sets, for which processing time and memory space arebounded by O(nmmu) and O(n+m), respectively, where n, m, andmu are the numbers of vertices, edges, and maximal independentsets of a graph. 1977 (Copyright) Society for Industrial and Applied Mathematics},\n author = {Tsukiyama, Shuji and Ide, Mikio and Ariyoshi, Hiromu and Shirakawa, Isao},\n doi = {10.1137/0206036},\n file = {:Users/KunihiroWASA/Dropbox/paper/1977/Tsukiyama et al., A New Algorithm for Generating All the Maximal Independent Sets, 1977.pdf:pdf},\n issn = {0097-5397},\n journal = {SIAM Journal on Computing},\n keywords = {1,4,6,algorithm,all the maximal independent,and is also interesting,backtracking,graph,in terms of complexity,introduction,is fundamental in the,its applications,maximal clique,maximal cliques,maximal independent set,of computation,or,sets,the efficient search for,theory of graphs and},\n month = {September},\n number = {3},\n pages = {505--517},\n title = {{A New Algorithm for Generating All the Maximal Independent Sets}},\n url = {http://epubs.siam.org/doi/abs/10.1137/0206036},\n volume = {6},\n year = {1977}\n}","bibtype":"article","doi":"10.1137/0206036","file":":Users/KunihiroWASA/Dropbox/paper/1977/Tsukiyama et al., A New Algorithm for Generating All the Maximal Independent Sets, 1977.pdf:pdf","id":"Tsukiyama1977a","issn":"0097-5397","journal":"SIAM Journal on Computing","key":"Tsukiyama1977a","keywords":"1,4,6,algorithm,all the maximal independent,and is also interesting,backtracking,graph,in terms of complexity,introduction,is fundamental in the,its applications,maximal clique,maximal cliques,maximal independent set,of computation,or,sets,the efficient search for,theory of graphs and","month":"September","number":"3","pages":"505--517","title":"A New Algorithm for Generating All the Maximal Independent Sets","type":"article","url":"http://epubs.siam.org/doi/abs/10.1137/0206036","volume":"6","year":"1977","bibbaseid":"tsukiyama-ide-ariyoshi-shirakawa-anewalgorithmforgeneratingallthemaximalindependentsets-1977","role":"author","urls":{"Paper":"http://epubs.siam.org/doi/abs/10.1137/0206036"},"keyword":["1","4","6","algorithm","all the maximal independent","and is also interesting","backtracking","graph","in terms of complexity","introduction","is fundamental in the","its applications","maximal clique","maximal cliques","maximal independent set","of computation","or","sets","the efficient search for","theory of graphs and"],"downloads":0,"html":""},"bibtype":"article","biburl":"http://www-ikn.ist.hokudai.ac.jp/~wasa/enum.bib","creationDate":"2015-04-23T04:51:45.505Z","downloads":0,"keywords":["1","4","6","algorithm","all the maximal independent","and is also interesting","backtracking","graph","in terms of complexity","introduction","is fundamental in the","its applications","maximal clique","maximal cliques","maximal independent set","of computation","or","sets","the efficient search for","theory of graphs and"],"search_terms":["new","algorithm","generating","maximal","independent","sets","tsukiyama","ide","ariyoshi","shirakawa"],"title":"A New Algorithm for Generating All the Maximal Independent Sets","year":1977,"dataSources":["YRMeqhMHoNu9HzJoC"]}