2024-10-13T00:27:30Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:002045272024-03-29T05:26:34Z01164:02592:10084:10210
Another Time-Complexity Analysis for Maximal Clique Enumeration Algorithm CLIQUESAnother Time-Complexity Analysis for Maximal Clique Enumeration Algorithm CLIQUESenghttp://id.nii.ac.jp/1001/00204432/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=204527&item_no=1&attribute_id=1&file_no=1Copyright (c) 2020 by the Institute of Electronics, Information and Communication Engineers This SIG report is only available to those in membership of the SIG.The Advanced Algorithms Research Laboratory, The University of Electro-CommunicationsDepartment of Computer Science, University of PisaEtsuji, TomitaAlessio, ConteWe revisit the maximal clique enumeration algorithm CLIQUES that appeared in Theoretical Computer Science 2006. It is proved to work in O (3n/3) -time in the worst-case for an n vertex graph. In this note, we extend the time-complexity analysis with respect to the number of maximal cliques, an issue that was left as an open problem since TCS 2006.We revisit the maximal clique enumeration algorithm CLIQUES that appeared in Theoretical Computer Science 2006. It is proved to work in O (3n/3) -time in the worst-case for an n vertex graph. In this note, we extend the time-complexity analysis with respect to the number of maximal cliques, an issue that was left as an open problem since TCS 2006.AN1009593X研究報告アルゴリズム（AL）2020-AL-1787182020-05-022188-85662020-04-30