×

zbMATH — the first resource for mathematics

Weighted maximum-clique transversal sets of graphs. (English) Zbl 1237.05153
Summary: A maximum-clique transversal set of a graph \(G\) is a subset of vertices intersecting all maximum cliques of \(G\). The maximum-clique transversal set problem is to find a maximum-clique transversal set of \(G\) of minimum cardinality. Motivated by the placement of transmitters for cellular telephones, M.-S. Chang, T. Kloks and C.-M. Lee [Lect. Notes Comput. Sci. 2204, 32–43 (2001; Zbl 1042.68619)] introduced the concept of maximum-clique transversal sets on graphs. In this paper, we study the weighted version of the maximum-clique transversal set problem for split graphs, balanced graphs, strongly chordal graph, Helly circular-arc graphs, comparability graphs, distance-hereditary graphs, and graphs of bounded treewidth.

MSC:
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX XML Cite
Full Text: DOI
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. · Zbl 1042.68619 · doi:10.1007/3-540-45477-2_5 · link.springer.de
[2] C.-M. Lee, “Variations of maximum-clique transversal sets on graphs,” Annals of Operations Research, vol. 181, pp. 21-66, 2010. · Zbl 1235.90175 · doi:10.1007/s10479-009-0673-6
[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. · Zbl 0734.05077 · doi:10.1016/0012-365X(91)90055-7
[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. · Zbl 0846.05050 · doi:10.1016/0012-365X(94)00276-O
[5] T. Andreae, “On the clique-transversal number of chordal graphs,” Discrete Mathematics, vol. 191, no. 1-3, pp. 3-11, 1998. · Zbl 0955.05058 · doi:10.1016/S0012-365X(98)00087-9
[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. · doi:10.1016/0020-0190(96)00054-3
[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. · Zbl 0605.05024 · doi:10.1016/0095-8956(86)90043-2
[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. · Zbl 1080.05058 · doi:10.1007/s10107-005-0651-y
[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. · Zbl 0869.05048 · doi:10.1137/S0895480194267853
[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. · Zbl 0777.05085 · doi:10.1137/0406002
[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. · Zbl 0854.68072 · doi:10.1016/0166-218X(95)00048-V
[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. · Zbl 1338.68098 · doi:10.1016/S0020-0190(98)00019-2
[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. · Zbl 1104.05054 · doi:10.1016/j.dam.2006.03.022
[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. · Zbl 1163.90768 · doi:10.1007/s10479-007-0189-x
[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. · Zbl 1013.90107 · doi:10.1023/A:1021363810398
[16] P. Erd\Hos, T. Gallai, and Z. Tuza, “Covering the cliques of a graph with vertices,” Discrete Mathematics, vol. 108, no. 1-3, pp. 279-289, 1992. · Zbl 0766.05063 · doi:10.1016/0012-365X(92)90681-5
[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. · Zbl 0948.68135 · doi:10.1016/S0166-218X(99)00159-6
[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. · Zbl 1110.68108 · doi:10.1016/j.dam.2005.07.011
[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. · Zbl 1246.05123
[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. · Zbl 1125.05076 · doi:10.1016/j.amc.2006.12.027
[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. · Zbl 0919.05001
[22] D. R. Fulkerson, A. J. Hoffman, and R. Oppenheim, “On balanced matrices,” Mathematical Programming Study, no. 1, pp. 120-132, 1974. · Zbl 0357.90038
[23] E. Prisner, “Hereditary clique-Helly graphs,” Journal of Combinatorial Mathematics and Combinatorial Computing, vol. 14, pp. 216-220, 1993. · Zbl 0794.05113
[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. · Zbl 1095.68626 · doi:10.1007/b98413
[25] D. J. Rose, “Triangulated graphs and the elimination process,” Journal of Mathematical Analysis and Applications, vol. 32, pp. 597-609, 1970. · Zbl 0216.02602 · doi:10.1016/0022-247X(70)90282-9
[26] M. Farber, “Characterizations of strongly chordal graphs,” Discrete Mathematics, vol. 43, no. 2-3, pp. 173-189, 1983. · Zbl 0514.05048 · doi:10.1016/0012-365X(83)90154-1
[27] R. Paige and R. E. Tarjan, “Three partition refinement algorithms,” SIAM Journal on Computing, vol. 16, no. 6, pp. 973-989, 1987. · Zbl 0654.68072 · doi:10.1137/0216062
[28] J. P. Spinrad, “Doubly lexical ordering of dense 0-1 matrices,” Information Processing Letters, vol. 45, no. 5, pp. 229-235, 1993. · Zbl 0771.68068 · doi:10.1016/0020-0190(93)90209-R
[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. · Zbl 0227.05116 · doi:10.1137/0201013
[30] M. Farber, “Domination, independent domination, and duality in strongly chordal graphs,” Discrete Applied Mathematics, vol. 7, no. 2, pp. 115-130, 1984. · Zbl 0531.05045 · doi:10.1016/0166-218X(84)90061-1
[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. · Zbl 1341.05196
[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. · Zbl 0911.05051 · doi:10.1137/S0097539792238431
[33] R. M. McConnell and J. P. Spinrad, “Modular decomposition and transitive orientation,” Discrete Mathematics, vol. 201, no. 1-3, pp. 189-241, 1999. · Zbl 0933.05146 · doi:10.1016/S0012-365X(98)00319-7
[34] L. Rédei, “Ein Kombinatorischer Satz,” Acta Litteraria Szeged, vol. 7, pp. 39-43, 1934. · Zbl 0009.14606
[35] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, MIT Press, Cambridge, Mass, USA, 3rd edition, 2009. · Zbl 1187.68679
[36] L. R. Ford, Jr. and D. R. Fulkerson, “Maximal flow through a network,” Canadian Journal of Mathematics, vol. 8, pp. 399-404, 1956. · Zbl 0073.40203 · doi:10.4153/CJM-1956-045-5
[37] L. R. Ford, Jr. and D. R. Fulkerson, Flows in Networks, Princeton University Press, Princeton, NJ, USA, 1962. · Zbl 0106.34802
[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. · Zbl 0661.90031 · doi:10.1145/48014.61051
[39] T. Kloks, Treewidth-Computations and Approximation, vol. 842 of Lecture Notes in Computer Science, Springer, Berlin, Germany, 1994. · Zbl 0825.68144 · doi:10.1007/BFb0045375
[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. · Zbl 0864.68074 · doi:10.1137/S0097539793251219
[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. · Zbl 0773.05091 · doi:10.1137/0406014
[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. · Zbl 1153.68398 · doi:10.1016/j.tcs.2006.06.015
[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. · Zbl 1059.68598 · doi:10.1007/3-540-45995-2_52 · link.springer.de
[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. · doi:10.1007/3-540-63890-3_37
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.