{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T01:43:24Z","timestamp":1760233404861,"version":"build-2065373602"},"reference-count":30,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2021,1,13]],"date-time":"2021-01-13T00:00:00Z","timestamp":1610496000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001868","name":"National Science Council","doi-asserted-by":"publisher","award":["NSC-97-2218-E-130-002-MY2"],"award-info":[{"award-number":["NSC-97-2218-E-130-002-MY2"]}],"id":[{"id":"10.13039\/501100001868","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>This paper studies the maximum-clique independence problem and some variations of the clique transversal problem such as the {k}-clique, maximum-clique, minus clique, signed clique, and k-fold clique transversal problems from algorithmic aspects for k-trees, suns, planar graphs, doubly chordal graphs, clique perfect graphs, total graphs, split graphs, line graphs, and dually chordal graphs. We give equations to compute the {k}-clique, minus clique, signed clique, and k-fold clique transversal numbers for suns, and show that the {k}-clique transversal problem is polynomial-time solvable for graphs whose clique transversal numbers equal their clique independence numbers. We also show the relationship between the signed and generalization clique problems and present NP-completeness results for the considered problems on k-trees with unbounded k, planar graphs, doubly chordal graphs, total graphs, split graphs, line graphs, and dually chordal graphs.<\/jats:p>","DOI":"10.3390\/a14010022","type":"journal-article","created":{"date-parts":[[2021,1,13]],"date-time":"2021-01-13T11:52:32Z","timestamp":1610538752000},"page":"22","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Algorithmic Aspects of Some Variations of Clique Transversal and Clique Independent Sets on Graphs"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3456-6697","authenticated-orcid":false,"given":"Chuan-Min","family":"Lee","sequence":"first","affiliation":[{"name":"Department of Computer and Communication Engineering, Ming Chuan University, 5 De Ming Road, Guishan District, Taoyuan City 333, Taiwan"}]}],"member":"1968","published-online":{"date-parts":[[2021,1,13]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/S0166-218X(97)00034-6","article-title":"Transversal partitioning in balanced hypergraphs","volume":"79","author":"Dahlhaus","year":"1997","journal-title":"Discret. Math."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/S0020-0190(98)00019-2","article-title":"Maximum h-colourable subgraph problem in balanced graphs","volume":"65","author":"Dahlhaus","year":"1998","journal-title":"Inf. Process. Lett."},{"key":"ref_3","first-page":"32","article-title":"Maximum clique transversals","volume":"Volume 2204","author":"Chang","year":"2001","journal-title":"Proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/s10479-009-0673-6","article-title":"Variations of maximum-clique transversal sets on graphs","volume":"181","author":"Lee","year":"2010","journal-title":"Ann. Oper. Res."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1016\/j.ipl.2008.12.019","article-title":"Signed and minus clique-transversal function on graphs","volume":"109","author":"Lee","year":"2009","journal-title":"Inf. Process. Lett."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"2398","DOI":"10.1080\/00207160902822330","article-title":"Signed clique-transversal functions in graphs","volume":"87","author":"Wang","year":"2010","journal-title":"Int. J. Comput. Math."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1410","DOI":"10.1016\/j.amc.2006.12.027","article-title":"The algorithmic complexity of the minus clique-transversal problem","volume":"189","author":"Xu","year":"2007","journal-title":"Appl. Math. Comput."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0166-218X(95)00048-V","article-title":"Algorithmic aspects of the generalized clique transversal problem on chordal graphs","volume":"66","author":"Chang","year":"1996","journal-title":"Discret. Appl. Math."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"4185","DOI":"10.1016\/j.disc.2007.08.080","article-title":"Variations of Y-dominating functions on graphs","volume":"308","author":"Lee","year":"2008","journal-title":"Discret. Math."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0020-0190(96)00054-3","article-title":"Clique transversal and clique independence on comparability graphs","volume":"58","author":"Balachandran","year":"1996","journal-title":"Inf. Process. Lett."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1016\/j.dam.2005.07.011","article-title":"Distance-hereditary graphs are clique-perfect","volume":"154","author":"Lee","year":"2006","journal-title":"Discret. Appl. Math."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1007\/s10107-005-0651-y","article-title":"On balanced graphs","volume":"105","author":"Bonomo","year":"2006","journal-title":"Math. Program."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/0012-365X(86)90031-2","article-title":"Neighborhood perfect graphs","volume":"61","author":"Lehel","year":"1986","journal-title":"Discret. Math."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1137\/0406002","article-title":"Algorithmic aspects of neighborhood numbers","volume":"6","author":"Chang","year":"1993","journal-title":"SIAM J. Discret. Math."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1007\/BFb0121244","article-title":"On balnaced matrices","volume":"1","author":"Fulkerson","year":"1974","journal-title":"Math. Program. Study"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"556","DOI":"10.1016\/j.ipl.2015.01.007","article-title":"On the complexity of {k}-domination and k-tuple domination in graphs","volume":"115","author":"Argiroffo","year":"2015","journal-title":"Inf. Process. Lett."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1016\/j.disopt.2016.04.002","article-title":"On complexities of minus domination","volume":"22","author":"Faria","year":"2016","journal-title":"Discret. Optim."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/S0020-0190(03)00233-3","article-title":"k-tuple domination in graphs","volume":"87","author":"Liao","year":"2003","journal-title":"Inf. Process. Lett."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Le, V.B., and Spinrad, J.P. (1999). Graph Classes\u2013A Survey, SIAM Monographs on Discrete Math and Applications, Society for Industrial and Applied Mathematics.","DOI":"10.1137\/1.9780898719796"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","article-title":"Incidence matrices and interval graphs","volume":"15","author":"Fulkerson","year":"1965","journal-title":"Pac. J. Math."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1137\/S0895480193253415","article-title":"Dually chordal graphs","volume":"11","author":"Dragan","year":"1998","journal-title":"SIAM J. Discret. Math."},{"key":"ref_22","first-page":"64","article-title":"HT-graphs: Centers, connected r-domination, and Steiner trees","volume":"1","author":"Dragan","year":"1993","journal-title":"Comput. Sci. J. Mold."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/net.3230230108","article-title":"Doubly chordal graphs, Steiner trees, and connected domination","volume":"23","author":"Moscarini","year":"1993","journal-title":"Networks"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1016\/S0166-218X(99)00028-1","article-title":"Recognizing clique graphs of directed and rooted path graphs","volume":"94","author":"Prisner","year":"1999","journal-title":"Discret. Appl. Math."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1137\/S0895480194267853","article-title":"Clique r-domination and clique r-packing problems on dually chordal graphs","volume":"10","author":"Chepoi","year":"1997","journal-title":"SIAM J. Discret. Math."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1016\/0022-247X(70)90282-9","article-title":"Triangulated graphs and the elimination process","volume":"32","author":"Rose","year":"1970","journal-title":"J. Math. Anal. Appl."},{"key":"ref_27","first-page":"57","article-title":"On the structure of k-trees","volume":"11","author":"Patil","year":"1986","journal-title":"J. Comb. Inf. Syst. Sci."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/S0166-218X(99)00159-6","article-title":"Algorithmic aspects of clique-transversal and clique-independent sets","volume":"100","author":"Guruswami","year":"2000","journal-title":"Discret. Appl. Math."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1007\/s00373-007-0738-8","article-title":"On the maximum number of cliques in a graph","volume":"23","author":"Wood","year":"2007","journal-title":"Graphs Comb."},{"key":"ref_30","unstructured":"Uehara, R. (1996). NP-Complete Problems on a 3-Connected Cubic Planar Graph and Their Applications, Tokyo Woman\u2019s Christian University. Technical Report TWCU-M-0004."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/1\/22\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:10:41Z","timestamp":1760159441000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/1\/22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,13]]},"references-count":30,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2021,1]]}},"alternative-id":["a14010022"],"URL":"https:\/\/doi.org\/10.3390\/a14010022","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2021,1,13]]}}}