An efficient algorithm to generate all maximal independent sets on trapezoid graphs

References

• Chang , M.S. and Wang , F.H. 1992 . Efficient algorithms for the maximum weight clique and maximum weight independent set problems on permutation graphs . Information Processing Letters , 43 : 293 – 295 .
   Web of Science ®Google Scholar
• Cheah , F. and Corneil , D.G. 1996 . On the structure of trapezoid graphs . Discrete Applied Mathematics , 66 : 109 – 133 .
   Web of Science ®Google Scholar
• Dagan , I. , Golumbic , M.C. and Pinter , R.Y. 1988 . Trapezoid graphs and their coloring . Discrete Applied Mathematics , 21 : 35 – 46 .
   Web of Science ®Google Scholar
• Dahlhaus , E. and Karpinski , M. 1988 . A fast parallel algorithm for computing all maximal cliques in a graph and the related problems . First Scandinavian Workshop on Algorithm Theory , 318 : 139 – 144 . SWAT88, LNCS
   Google Scholar
• Gabor , C.P. , Hsu , W.L. and Supowit , K.J. . Recognizing circle graphs in polynomial time . Proc:26th IEEE FOCS . pp. 106 – 116 .
   Google Scholar
• Golumbic , M.C. 1980 . Algorithmic Graph Theory and Perfect Graphs , New York : Academic Press .
   Google Scholar
• Ho , C.W. and Lee , R.C.T. 1988 . Efficient parallel algorithms for finding maximal cliques, clique trees and minimum coloring on chorda! graphs . Information Processing Letters , 28 : 301 – 309 .
   Web of Science ®Google Scholar
• Kirsch , E.S. and Bair , J.R.S. 1991 . Practical parallel algorithms for chordal graphs . Advances in Computing and Information , 497 : 372 – 382 . IQCI′91, LNCS
   Google Scholar
• Klein , P.N. . Efficient parallel algorithms for chordal graphs . Proc:29th IEEE FOCS . pp. 150 – 161 .
   Google Scholar
• Leung , J.Y.T. 1984 . Fast Algorithms for Generating all Maximal Independent Sets of Interval, Circular-arc and Chordal Graphs . J. Algorithms , 5 : 22 – 35 .
   Web of Science ®Google Scholar
• Liang , Y.D. 1994 . Domination in trapezoid graphs . Information Processing Letters , 52 : 309 – 315 .
   Google Scholar
• Masuda , S. , Nakajima , K. , Kaskwabara , T. and Fujisawa , T. 1987 . Efficient enumeration of maximal and maximum independent sets of an interval graph and a circular-arc graph , College Park, Md : University of Maryland . Technical Report UMIACS-TR-87-33
   Google Scholar
• Ma , T.H. and Spinrad , J.P. 1994 . On the 2-chain subgraph cover and related problems . J. Algorithms , 17 : 251 – 268 .
   Google Scholar
• Naor , J. , Naor , M. and Schaffer , A.A. 1989 . Fast parallel algorithms for chordal graphs . SIAM J. Comput , 18 : 327 – 349 .
   Web of Science ®Google Scholar
• Pal , M. and Bhattacharjee , G.P. 1995 . “ An optimal parallel algorithm for computing all maximal cliques of an interval graph and its applications ” . In J. Institution of Engineer Vol. 76 , 29 – 33 . India
   Google Scholar
• Pal , M. 1995 . Some Sequential and Parallel Algorithms on Interval Graphs , Kharagpur, , India : Indian Institute of Technology . Ph.D Thesis
   Google Scholar
• Pal , M. and Bhattacharjee , G.P. 1996 . A sequential algorithm for finding a maximum weight k-independent set on interval graphs . Intern. J, Computer Maths , 60 : 205 – 214 .
   Web of Science ®Google Scholar
• Pal , M. 1998 . A parallel algorithm to generate all maximal independent sets on permutation graphs . Intern. J. Computer Mathematics , 67 : 261 – 274 .
   Web of Science ®Google Scholar
• Pal M. An efficient algorithm to compute a maximum weight k-independent set on Permutation graphs, Communicated.
   Google Scholar
• Rotem , D. and Urrutia , J. 1981 . Finding maximum cliques in circle graphs . Networks , 11 : 269 – 278 .
   Web of Science ®Google Scholar
• Tsukiyama , S. , Ide , M. , Ariyoshi , H. and Shirakawa , I. 1977 . A new algorithm for generating all the maximal independent sets . SI AM J. Comput , 6 : 505 – 517 .
   Google Scholar
• Yu , C.W. and Chen , G.H. 1993 . Intern.J.Comput.Math , 47 : 1 – 8 .
   Web of Science ®Google Scholar