Linear-time algorithm for the matched-domination problem in cographs

References

• Bandelt , H. J. and Mulder , H. M. 1986 . Distance-hereditary graphs . J. Combin. Theory Ser. B , 41 : 182 – 208 .
   Web of Science ®Google Scholar
• Bodlaender , H. L. 1989 . Achromatic number is NP-complete for cographs and interval graphs . Inform. Process. Lett. , 31 : 135 – 138 .
   Web of Science ®Google Scholar
• Bodlaender , B. L. and Mohring , R. H. 1993 . The pathwidth and treewidth of cographs . SIAM J. Discrete Math. , 6 : 181 – 188 .
   Web of Science ®Google Scholar
• Chang , M. S. , Hsieh , S. Y. and Chen , G. H. 1997 . Dynamic Programming on Distance-Hereditary Graphs , Vol. 1350 , 344 – 353 . Berlin : Springer . Lecture Notes in Computer Science
   Google Scholar
• Chang , G. J. , Huang , L. H. and Yeh , H. G. 2008 . On the rank of a cograph . Linear Algebra Appl. , 429 : 601 – 605 .
   Web of Science ®Google Scholar
• Chen , L. , Lu , C. and Zeng , Z. 2010 . Labelling algorithms for paired-domination problems in block and interval graphs . J. Comb. Optim. , 19 : 457 – 470 .
   Web of Science ®Google Scholar
• Cheng , T. C.E. , Kang , L. and Ng , C. T. 2007 . Paired domination on interval and circular-arc graphs . Discrete Appl. Math. , 155 : 2077 – 2086 .
   Web of Science ®Google Scholar
• Cheng , T. C.E. , Kang , L. and Shan , E. 2009 . A polynomial-time algorithm for the paired-domination problem on permutation graphs . Discrete Appl. Math. , 157 : 262 – 271 .
   Web of Science ®Google Scholar
• Corneil , D. G. , Lerchs , H. and Stewart , L. K. 1981 . Complement reducible graphs . Discrete Appl. Math. , 3 : 163 – 174 .
   Web of Science ®Google Scholar
• Corneil , D. G. , Perl , Y. and Stewart , L. K. 1985 . A linear recognition algorithm for cographs . SIAM J. Comput. , 14 : 926 – 934 .
   Web of Science ®Google Scholar
• Damiand , G. , Habib , M. and Paul , C. 2001 . A simple paradigm for graph recognition: application to cographs and distance hereditary graphs . Theoret. Comput. Sci. , 263 : 99 – 111 .
   Web of Science ®Google Scholar
• Habib , M. and Paul , C. 2005 . A simple linear time recognition for cograph recognition . Discrete Appl. Math. , 145 : 183 – 197 .
   Web of Science ®Google Scholar
• Haynes , T. W. and Slater , P. J. 1998 . Paired-domination in graphs . Networks , 32 : 199 – 206 .
   Web of Science ®Google Scholar
• Haynes , T. W. , Hedetniemi , S. T. and Slater , P. J. 1998 . Fundamentals of Domination in Graphs , New York : Marcel Dekker .
   Google Scholar
• Haynes , T. W. , Hedetniemi , S. T. and Slater , P. J. 1998 . Domination in Graphs: Advanced Topics , New York : Marcel Dekker .
   Google Scholar
• Hsieh , S. Y. 2007 . A faster parallel connectivity algorithm on cographs . Appl. Math. Lett. , 20 : 341 – 344 .
   Web of Science ®Google Scholar
• Hung , R. W. 2006 . A linear-time algorithm for the terminal path cover problem in cographs . Proceedings of the 23rd Workshop on Combinatorial Mathematics and Computation Theory . 2006 , Changhwa, Taiwan. pp. 62 – 75 . Available at http://algo2006.csie.dyu.edu.tw/paper/1/B14.pdf
   Google Scholar
• Larrión , F. , de Mello , C. P. , Morgana , A. , Neumann-Lara , V. and Pizaña , M. A. 2004 . The clique operator on cographs and serial graphs . Discrete Math. , 282 : 183 – 191 .
   Web of Science ®Google Scholar
• Lerchs , H. 1971 . “ On cliques and kernels ” . Toronto : Department of Computer Science, University of Toronto . Tech. Rep
   Google Scholar
• Nakano , K. , Olariu , S. and Zomaya , A. Y. 2003 . A time-optimal solution for the path cover problem on cographs . Theoret. Comput. Sci. , 290 : 1541 – 1556 .
   Web of Science ®Google Scholar
• Nikolopoulos , S. D. and Palios , L. 2005 . Efficient parallel recognition of cographs . Discrete Appl. Math. , 150 : 182 – 215 .
   Web of Science ®Google Scholar
• Qiao , H. , Kang , L. , Cardei , M. and Du , D. Z. 2003 . Paired-domination of trees . J. Global Optim. , 25 : 43 – 54 .
   Web of Science ®Google Scholar
• Retoré , C. 2003 . Handsome proof-nets: perfect matchings and cographs . Theoret. Comput. Sci. , 294 : 473 – 488 .
   Web of Science ®Google Scholar
• Shamir , R. and Sharan , R. 2004 . A fully dynamic algorithm for modular decomposition and recognition of cographs . Discrete Appl. Math. , 136 : 329 – 340 .
   Web of Science ®Google Scholar
• Yu , M. S. and Yang , C. H. 1993 . An O(n) time algorithm for maximum matching on cographs . Inform. Process. Lett. , 47 : 89 – 93 .
   Web of Science ®Google Scholar