A parallel algorithm to generate all maximal independent sets on permutation graphs

References

• Bertossi , A.A. and Bonuccelli , M.A. 1987 . Some parallel algorithms on interval graphs . Discrete Applied Mathematics , 16 : 101 – 111 .
   Google Scholar
• 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
• Chen , C.C.Y. , Das , S.K. and Akl , S.G. 1991 . A unified approach to parallel depth-first traversals of general trees . Information Processing Letters , 38 : 49 – 55 .
   Web of Science ®Google Scholar
• Chen , L. 1992 . Optimal parallel time bounds for the maximum clique problem on intervals . Information Processing Letters , 42 : 197 – 201 .
   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 Scadinavian Workshop on Algorithm Theory , 318 : 139 – 144 . SWAT88, LNCS
   Google Scholar
• Gabor , C.P. , Hsu , W.L. and Supowit , K.J. 1985 . Recognizing circle graphs in polynomial time . In Proc: 26th IEEE FOCS , 318 : 106 – 116 .
   Google Scholar
• Gavril , F. 1972 . Algorithms for minimum coloring, maximum clique, minimum coloring by cliques and maximum independent sets of a chordal graph . SIAM J. Comput , 1 : 180 – 187 .
   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 chordal 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 . ICCI′91, LNCS
   Google Scholar
• Klein , P.N. 1988 . Efficient parallel algorithms for chordal graphs . In Proc: 29th IEEE FOCS , 497 : 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
• 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
• 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. An optimal parallel algorithm to solve the all-pair shortest path problem on an interval graph . In Proc: 3rd National Seminar on Theoretical Computer Science . Kharagpur, India. pp. 309 – 318 .
   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 . J. Institution of Engineer(India) , 76 : 29 – 33 .
   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. An efficient parallel algorithm for computing a maximum-weight independent set on permutation graphs . In Proc: 6th National Seminar on Theoretical Computer Science . Rajasthan, India. pp. 276 – 285 .
   Google Scholar
• Rotem , D. and Urrutia , J. 1981 . Finding maximum cliques in circle graphs . Networks , : 269 – 278 .
   Google Scholar
• Tsukiyama , S. , Ide , M. , Ariyoshi , H. and Shirakawa , I. 1977 . A new algorithm for generating all the maximal independent sets . SIAM J. Comput , 6 : 505 – 517 .
   Google Scholar
• Yu , C.W. and Chen , G.H. 1992 . The weighted maximum independent set problem in ermutation graphs . BIT , 32 : 609 – 618 .
   Google Scholar
• Yu , C.W. and Chen , G.H. 1993 . Generate all maximal independent sets in permutation graphs . Intern. J. Comput. Math , 47 : 1 – 8 .
   Web of Science ®Google Scholar
• Yu , M.S. , Tseng , L.Y. and Chang , S.J. 1993 . Sequential and parallel algorithms for the maximum weight independent set problem on permutation graphs . Information Processing Letters , 46 : 7 – 11 .
   Google Scholar