{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T13:29:10Z","timestamp":1753882150272,"version":"3.41.2"},"reference-count":25,"publisher":"World Scientific Pub Co Pte Ltd","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2023,8]]},"abstract":"<jats:p> In this paper, we analyze the intersection graphs of subtrees in a cactus, called cactus subtree graphs. A max-k-clique subgraph of a graph is an induced subgraph whose maximum clique has at most [Formula: see text] vertices. We describe a polynomial time algorithm to find a maximum weight max-[Formula: see text]-clique subgraph in a cactus subtree graph when [Formula: see text] is fixed. In perfect graphs this problem is equivalent to the maximum weight [Formula: see text]-colorable subgraph problem. In many applications like scheduling production lines and communication networks on imperfect graphs, a maximum max-[Formula: see text]-clique subgraph solution is better than a maximum [Formula: see text]-colorable subgraph solution. In addition, we describe cactus subtree graphs polynomial time algorithms for recognition, maximum independent sets, maximum cliques, maximum induced bipartite graphs, maximum induced forests and minimum feedback vertex sets. <\/jats:p>","DOI":"10.1142\/s1793830922501476","type":"journal-article","created":{"date-parts":[[2022,9,30]],"date-time":"2022-09-30T07:45:55Z","timestamp":1664523955000},"source":"Crossref","is-referenced-by-count":0,"title":["Maximum max-k-clique subgraphs in cactus subtree graphs"],"prefix":"10.1142","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9584-2232","authenticated-orcid":false,"given":"Fanica","family":"Gavril","sequence":"first","affiliation":[{"name":"Computer Science Department, Technion, Haifa, Israel"}]}],"member":"219","published-online":{"date-parts":[[2022,9,30]]},"reference":[{"key":"S1793830922501476BIB001","first-page":"622","volume-title":"Proc. 31st Annual ACM Symp. on Theory of Computing (STOC)","author":"Bar-Noy A.","year":"1999"},{"key":"S1793830922501476BIB002","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.disc.2003.05.001","volume":"278","author":"Cameron K.","year":"2004","journal-title":"Discrete Math."},{"key":"S1793830922501476BIB003","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1016\/j.ipl.2007.07.004","volume":"104","author":"Enright G.","year":"2007","journal-title":"Inform. Proc. Lett."},{"key":"S1793830922501476BIB004","first-page":"128","volume-title":"Proc. 4th Annual ACM-SIAM Symp. on Discrete Algorithms","author":"Eschen E. M.","year":"1993"},{"key":"S1793830922501476BIB005","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1137\/0601025","volume":"1","author":"Garey M. R.","year":"1980","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"S1793830922501476BIB006","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0095-8956(74)90094-X","volume":"16","author":"Gavril F.","year":"1974","journal-title":"J. Combin. Theory Ser. B"},{"key":"S1793830922501476BIB007","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1002\/net.3230040407","volume":"4","author":"Gavril F.","year":"1974","journal-title":"Networks"},{"key":"S1793830922501476BIB008","first-page":"645","volume":"6","author":"Gavril F.","year":"1996","journal-title":"Discrete Appl. Math."},{"key":"S1793830922501476BIB009","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/0012-365X(77)90030-9","volume":"19","author":"Gavril F.","year":"1997","journal-title":"Discrete Math."},{"key":"S1793830922501476BIB010","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/S0020-0190(00)00025-9","volume":"73","author":"Gavril F.","year":"2000","journal-title":"Inform. Proc. Lett."},{"key":"S1793830922501476BIB011","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/S0020-0190(01)00222-8","volume":"81","author":"Gavril F.","year":"2002","journal-title":"Inform. Proc. Lett."},{"key":"S1793830922501476BIB012","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1007\/978-3-642-02029-2_3","volume-title":"Graph Theory, Computational Intelligence and Thought","volume":"5420","author":"Gavril F.","year":"2009"},{"key":"S1793830922501476BIB013","first-page":"17","volume":"35","author":"Gavril F.","year":"2015","journal-title":"J. Discrete Math."},{"key":"S1793830922501476BIB014","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1016\/j.ipl.2017.08.007","volume":"128","author":"Gavril F.","year":"2017","journal-title":"Inform. Proc. Lett."},{"key":"S1793830922501476BIB015","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0012-365X(83)90019-5","volume":"43","author":"Golumbic M. C.","year":"1983","journal-title":"Discrete Math."},{"key":"S1793830922501476BIB016","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1137\/S0097539793260726","volume":"24","author":"Hsu W.-L.","year":"1995","journal-title":"SIAM J. Comput."},{"key":"S1793830922501476BIB017","series-title":"Algorithm Theory \u2014 SWAT 2006, Lecture Notes in Computer Science","first-page":"41","volume-title":"Scandinavian Workshop on Algorithm Theory","volume":"4059","author":"Kaplan H.","year":"2006"},{"key":"S1793830922501476BIB018","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/S0012-365X(96)00344-5","volume":"163","author":"Kratochvil G.","year":"1997","journal-title":"Discrete Math."},{"key":"S1793830922501476BIB019","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1007\/s00453-003-1032-7","volume":"37","author":"McConnell R.","year":"2003","journal-title":"Algorithmica"},{"key":"S1793830922501476BIB020","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1007\/978-3-540-74839-7_23","volume-title":"Graph-Theoretic Concepts in Computer Science","volume":"4769","author":"Pergel M.","year":"2007"},{"key":"S1793830922501476BIB021","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/0012-365X(85)90051-2","volume":"55","author":"Tarjan R. E.","year":"1985","journal-title":"Discrete Math."},{"key":"S1793830922501476BIB022","series-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1090\/dimacs\/046\/02","volume-title":"Multichannel Optical Networks Theory and Practice","volume":"46","author":"Wan P. G.","year":"1998"},{"key":"S1793830922501476BIB023","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"593","DOI":"10.1007\/978-3-319-60033-8_51","volume-title":"Wireless Algorithms, Systems, and Applications","volume":"10251","author":"Wan P. G.","year":"2017"},{"key":"S1793830922501476BIB024","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/0020-0190(81)90072-7","volume":"12","author":"Whitesides S. H.","year":"1981","journal-title":"Inform Proc. Lett."},{"key":"S1793830922501476BIB025","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0020-0190(87)90107-4","volume":"24","author":"Yannakakis M.","year":"1987","journal-title":"Inform. Proc. Lett."}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830922501476","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,8]],"date-time":"2023-06-08T08:41:18Z","timestamp":1686213678000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S1793830922501476"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,30]]},"references-count":25,"journal-issue":{"issue":"06","published-print":{"date-parts":[[2023,8]]}},"alternative-id":["10.1142\/S1793830922501476"],"URL":"https:\/\/doi.org\/10.1142\/s1793830922501476","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"type":"print","value":"1793-8309"},{"type":"electronic","value":"1793-8317"}],"subject":[],"published":{"date-parts":[[2022,9,30]]},"article-number":"2250147"}}