ISRN Discrete Mathematics
Volume 2011 (2011), Article ID 540834, 20 pages
doi:10.5402/2011/540834
Research Article

Weighted Maximum-Clique Transversal Sets of Graphs

Chuan-Min Lee

Department of Computer and Communication Engineering, Ming Chuan University, 5 De Ming Road, Guishan District, Taoyuan County 333, Taiwan

Received 16 November 2011; Accepted 26 December 2011

Academic Editors: E. Cheng, A. Pêcher, and E. Tomita

Copyright © 2011 Chuan-Min Lee. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Linked References

  1. M.-S. Chang, T. Kloks, and C.-M. Lee, “Maximum clique transversals,” in Proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science, vol. 2204 of Lecture Notes in Computer Science, pp. 32–43, 2001. View at Publisher · View at Google Scholar · View at Zentralblatt MATH
  2. C.-M. Lee, “Variations of maximum-clique transversal sets on graphs,” Annals of Operations Research, vol. 181, pp. 21–66, 2010. View at Publisher · View at Google Scholar
  3. T. Andreae, M. Schughart, and Z. Tuza, “Clique-transversal sets of line graphs and complements of line graphs,” Discrete Mathematics, vol. 88, no. 1, pp. 11–20, 1991. View at Publisher · View at Google Scholar · View at Zentralblatt MATH · View at MathSciNet
  4. T. Andreae and C. Flotow, “On covering all cliques of a chordal graph,” Discrete Mathematics, vol. 149, no. 1–3, pp. 299–302, 1996. View at Publisher · View at Google Scholar · View at Zentralblatt MATH · View at MathSciNet
  5. T. Andreae, “On the clique-transversal number of chordal graphs,” Discrete Mathematics, vol. 191, no. 1–3, pp. 3–11, 1998. View at Publisher · View at Google Scholar · View at Zentralblatt MATH · View at MathSciNet
  6. V. Balachandran, P. Nagavamsi, and C. P. Rangan, “Clique transversal and clique independence on comparability graphs,” Information Processing Letters, vol. 58, no. 4, pp. 181–184, 1996. View at Publisher · View at Google Scholar · View at MathSciNet
  7. H.-J. Bandelt and H. M. Mulder, “Distance-hereditary graphs,” Journal of Combinatorial Theory. Series B, vol. 41, no. 2, pp. 182–208, 1986. View at Publisher · View at Google Scholar · View at Zentralblatt MATH · View at MathSciNet
  8. F. Bonomo, G. Durán, M. C. Lin, and J. L. Szwarcfiter, “On balanced graphs,” Mathematical Programming, vol. 105, no. 2-3, pp. 233–250, 2006. View at Publisher · View at Google Scholar · View at Zentralblatt MATH · View at MathSciNet
  9. A. Brandstädt, V. D. Chepoi, and F. F. Dragan, “Clique r-domination and clique r-packing problems on dually chordal graphs,” SIAM Journal on Discrete Mathematics, vol. 10, no. 1, pp. 109–127, 1997. View at Publisher · View at Google Scholar · View at MathSciNet
  10. G. J. Chang, M. Farber, and Z. Tuza, “Algorithmic aspects of neighborhood numbers,” SIAM Journal on Discrete Mathematics, vol. 6, no. 1, pp. 24–29, 1993. View at Publisher · View at Google Scholar · View at Zentralblatt MATH · View at MathSciNet
  11. M.-S. Chang, Y.-H. Chen, G. J. Chang, and J.-H. Yan, “Algorithmic aspects of the generalized clique-transversal problem on chordal graphs,” Discrete Applied Mathematics, vol. 66, no. 3, pp. 189–203, 1996. View at Publisher · View at Google Scholar · View at Zentralblatt MATH · View at MathSciNet
  12. E. Dahlhaus, P. D. Manuel, and M. Miller, “Maximum h-colourable subgraph problem in balanced graphs,” Information Processing Letters, vol. 65, no. 6, pp. 301–303, 1998. View at Publisher · View at Google Scholar · View at MathSciNet
  13. G. Durán, M. C. Lin, S. Mera, and J. L. Szwarcfiter, “Algorithms for clique-independent sets on subclasses of circular-arc graphs,” Discrete Applied Mathematics, vol. 154, no. 13, pp. 1783–1790, 2006. View at Publisher · View at Google Scholar · View at Zentralblatt MATH · View at MathSciNet
  14. G. Durán, M. C. Lin, S. Mera, and J. L. Szwarcfiter, “Algorithms for finding clique-transversals of graphs,” Annals of Operations Research, vol. 157, pp. 37–45, 2008. View at Publisher · View at Google Scholar · View at Zentralblatt MATH · View at MathSciNet
  15. G. Durán, M. C. Lin, and J. L. Szwarcfiter, “On clique-transversals and clique-independent sets,” Annals of Operations Research, vol. 116, pp. 71–77, 2002. View at Publisher · View at Google Scholar · View at Zentralblatt MATH · View at MathSciNet
  16. P. Erdős, T. Gallai, and Z. Tuza, “Covering the cliques of a graph with vertices,” Discrete Mathematics, vol. 108, no. 1-3, pp. 279–289, 1992. View at Publisher · View at Google Scholar · View at MathSciNet
  17. V. Guruswami and C. P. Rangan, “Algorithmic aspects of clique-transversal and clique-independent sets,” Discrete Applied Mathematics, vol. 100, no. 3, pp. 183–202, 2000. View at Publisher · View at Google Scholar · View at Zentralblatt MATH · View at MathSciNet
  18. C.-M. Lee and M.-S. Chang, “Distance-hereditary graphs are clique-perfect,” Discrete Applied Mathematics, vol. 154, no. 3, pp. 525–536, 2006. View at Publisher · View at Google Scholar · View at Zentralblatt MATH · View at MathSciNet
  19. E. Shan, Z. Liang, and T. C. E. Cheng, “Clique-transversal number in cubic graphs,” Discrete Mathematics & Theoretical Computer Science. DMTCS., vol. 10, no. 2, pp. 115–124, 2008.
  20. G. Xu, E. Shan, L. Kang, and T. C. E. Cheng, “The algorithmic complexity of the minus clique-transversal problem,” Applied Mathematics and Computation, vol. 189, no. 2, pp. 1410–1418, 2007. View at Publisher · View at Google Scholar · View at Zentralblatt MATH · View at MathSciNet
  21. A. Brandstädt, V. B. Le, and J. P. Spinrad, “Graph classes—a Survey,” SIAM Monographs on Discrete Mathematics and Applications, Society for Industrial and Applied Mathematics, Philadelphia, Pa, USA, 1999.
  22. D. R. Fulkerson, A. J. Hoffman, and R. Oppenheim, “On balanced matrices,” Mathematical Programming Study, no. 1, pp. 120–132, 1974. View at Zentralblatt MATH
  23. E. Prisner, “Hereditary clique-Helly graphs,” Journal of Combinatorial Mathematics and Combinatorial Computing, vol. 14, pp. 216–220, 1993. View at Zentralblatt MATH
  24. K. Makino and T. Uno, “New algorithms for enumerating all maximal cliques,” in Proceedings of the 9th Scandinavian Workshop on Algorithm Theory, vol. 3111 of Lecture Notes in Computer Science, pp. 260–274, 2004. View at Publisher · View at Google Scholar · View at Zentralblatt MATH
  25. D. J. Rose, “Triangulated graphs and the elimination process,” Journal of Mathematical Analysis and Applications, vol. 32, pp. 597–609, 1970. View at Publisher · View at Google Scholar · View at Zentralblatt MATH
  26. M. Farber, “Characterizations of strongly chordal graphs,” Discrete Mathematics, vol. 43, no. 2-3, pp. 173–189, 1983. View at Publisher · View at Google Scholar · View at Zentralblatt MATH
  27. R. Paige and R. E. Tarjan, “Three partition refinement algorithms,” SIAM Journal on Computing, vol. 16, no. 6, pp. 973–989, 1987. View at Publisher · View at Google Scholar · View at Zentralblatt MATH · View at MathSciNet
  28. J. P. Spinrad, “Doubly lexical ordering of dense 0–1 matrices,” Information Processing Letters, vol. 45, no. 5, pp. 229–235, 1993. View at Publisher · View at Google Scholar · View at MathSciNet
  29. F. Gavril, “Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph,” SIAM Journal on Computing, vol. 1, no. 2, pp. 180–187, 1972. View at Publisher · View at Google Scholar · View at Zentralblatt MATH
  30. M. Farber, “Domination, independent domination, and duality in strongly chordal graphs,” Discrete Applied Mathematics, vol. 7, no. 2, pp. 115–130, 1984. View at Publisher · View at Google Scholar · View at Zentralblatt MATH · View at MathSciNet
  31. M. C. Lin, R. M. McConnell, F. J. Soulignac, and J. L. Szwarcfiter, “On cliques of Helly circular-arc graphs,” Electronic Notes in Discrete Mathematices, vol. 30, pp. 117–122, 2008.
  32. M.-S. Chang, “Efficient algorithms for the domination problems on interval and circular-arc graphs,” SIAM Journal on Computing, vol. 27, no. 6, pp. 1671–1694, 1998. View at Publisher · View at Google Scholar · View at Zentralblatt MATH · View at MathSciNet
  33. R. M. McConnell and J. P. Spinrad, “Modular decomposition and transitive orientation,” Discrete Mathematics, vol. 201, no. 1–3, pp. 189–241, 1999. View at Publisher · View at Google Scholar · View at Zentralblatt MATH · View at MathSciNet
  34. L. Rédei, “Ein Kombinatorischer Satz,” Acta Litteraria Szeged, vol. 7, pp. 39–43, 1934.
  35. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, MIT Press, Cambridge, Mass, USA, 3rd edition, 2009.
  36. L. R. Ford, Jr. and D. R. Fulkerson, “Maximal flow through a network,” Canadian Journal of Mathematics, vol. 8, pp. 399–404, 1956. View at Publisher · View at Google Scholar · View at Zentralblatt MATH
  37. L. R. Ford, Jr. and D. R. Fulkerson, Flows in Networks, Princeton University Press, Princeton, NJ, USA, 1962.
  38. A. V. Goldberg and R. E. Tarjan, “A new approach to the maximum-flow problem,” Journal of the Association for Computing Machinery, vol. 35, no. 4, pp. 921–940, 1988. View at Publisher · View at Google Scholar · View at Zentralblatt MATH
  39. T. Kloks, Treewidth—Computations and Approximation, vol. 842 of Lecture Notes in Computer Science, Springer, Berlin, Germany, 1994. View at Publisher · View at Google Scholar
  40. H. Bodlaender, “A linear-time algorithm for finding tree-decompositions of small treewidth,” SIAM Journal on Computing, vol. 25, no. 6, pp. 1305–1317, 1996. View at Publisher · View at Google Scholar · View at Zentralblatt MATH · View at MathSciNet
  41. H. Bodlaender and R. H. Möhring, “The pathwidth and treewidth of cographs,” SIAM Journal on Discrete Mathematics, vol. 6, no. 2, pp. 181–188, 1993. View at Publisher · View at Google Scholar · View at Zentralblatt MATH · View at MathSciNet
  42. E. Tomita, A. Tanaka, and H. Takahashi, “The worst-case time complexity for generating all maximal cliques and computational experiments,” Theoretical Computer Science, vol. 363, no. 1, pp. 28–42, 2006. View at Publisher · View at Google Scholar · View at Zentralblatt MATH · View at MathSciNet
  43. J. Alber and R. Niedermeier, “Improved tree decomposition based algorithms for domination-like problems,” in Proceedings of the LATIN, vol. 2286 of Lecture Notes in Computer Science, pp. 613–627, Springer, Berlin, Germany, 2002. View at Publisher · View at Google Scholar · View at Zentralblatt MATH
  44. M.-S. Chang, S.-y. Hsieh, and G.-H. Chen, “Dynamic programming on distance-hereditary graphs,” in Proceedings of the 8th International Syposium on Algorithms and Computation, vol. 1350 of Lecture Notes in Computer Science, pp. 344–353, 1997. View at Publisher · View at Google Scholar