Header menu link for other important links
Computation of all possible maximal cliques of a weakly triangulated graph in polynomial time
Published in Institute of Electrical and Electronics Engineers Inc.
Pages: 159 - 168
In this paper, we have addressed the computation of an invariant of weakly triangulated graph. The invariant computed here are all possible maximal cliques of the specific graph class. The logic of computing all possible maximal cliques of weakly triangulated graph is based on one of its prime characterization, i.e., existence of more than one 2-pair in a weakly triangulated graph. For each graph belonging to such a class there exists a sequence of 2-pairs whose successive merging leads the graph into a complete one. In a reverse way successive decomposition of vertices of the obtained complete graph ultimately yields some non-decomposable induced subgraph of the original weakly triangulated graph. These non-decomposable induced subgraphs are not only maximal cliques, but subcliques or redundant occurrences of the same maximal cliques. Our algorithm proposed in this paper, while breaking by 2-pairs produces only maximal cliques in O(n 3 log -E-) time for a weakly triangulated graph G = (V, E), where V = n. The paper along with the algorithm contains necessary theorems, lemmas, etc., proving that the algorithm invented here terminates successfully and produces the desired maximal cliques only. © 2014 The Science and Information (SAI) Organization.
About the journal
JournalData powered by TypesetProceedings of 2014 Science and Information Conference, SAI 2014
PublisherData powered by TypesetInstitute of Electrical and Electronics Engineers Inc.
Open AccessNo