{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T04:17:39Z","timestamp":1740111459206,"version":"3.37.3"},"reference-count":34,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2018,12,1]],"date-time":"2018-12-01T00:00:00Z","timestamp":1543622400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2022,12,31]],"date-time":"2022-12-31T00:00:00Z","timestamp":1672444800000},"content-version":"vor","delay-in-days":1491,"URL":"http:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"},{"start":{"date-parts":[[2018,12,1]],"date-time":"2018-12-01T00:00:00Z","timestamp":1543622400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2018,12,1]],"date-time":"2018-12-01T00:00:00Z","timestamp":1543622400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2018,12,1]],"date-time":"2018-12-01T00:00:00Z","timestamp":1543622400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2018,12,1]],"date-time":"2018-12-01T00:00:00Z","timestamp":1543622400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2018,12,1]],"date-time":"2018-12-01T00:00:00Z","timestamp":1543622400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"funder":[{"DOI":"10.13039\/501100004663","name":"Ministry of Science and Technology of Taiwan","doi-asserted-by":"crossref","award":["NSC\u00a0101\u20132221\u2013E\u2013241\u2013019\u2013MY3","NSC\u00a0102\u20132221\u2013E\u2013241\u2013007\u2013MY3"],"award-info":[{"award-number":["NSC\u00a0101\u20132221\u2013E\u2013241\u2013019\u2013MY3","NSC\u00a0102\u20132221\u2013E\u2013241\u2013007\u2013MY3"]}],"id":[{"id":"10.13039\/501100004663","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[2018,12]]},"DOI":"10.1016\/j.dam.2018.05.032","type":"journal-article","created":{"date-parts":[[2018,6,15]],"date-time":"2018-06-15T14:17:25Z","timestamp":1529072245000},"page":"114-125","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":3,"special_numbering":"C","title":["Moderately exponential time algorithms for the maximum bounded-degree-1 set problem"],"prefix":"10.1016","volume":"251","author":[{"given":"Maw-Shang","family":"Chang","sequence":"first","affiliation":[]},{"given":"Li-Hsuan","family":"Chen","sequence":"additional","affiliation":[]},{"given":"Ling-Ju","family":"Hung","sequence":"additional","affiliation":[]},{"given":"Yi-Zhi","family":"Liu","sequence":"additional","affiliation":[]},{"given":"Peter","family":"Rossmanith","sequence":"additional","affiliation":[]},{"given":"Somnath","family":"Sikdar","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/j.dam.2018.05.032_b1","doi-asserted-by":"crossref","unstructured":"B. Balasundaram, Cohesive subgroup model for graph-based text mining, in: Proceedings of the 2008 IEEE Conference on Automation Science and Engineering, 2008, pp. 989\u2013994.","DOI":"10.1109\/COASE.2008.4626551"},{"key":"10.1016\/j.dam.2018.05.032_b2","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1287\/opre.1100.0851","article-title":"Clique relaxations in social network analysis: The maximum k-plex problem","volume":"59","author":"Balasundaram","year":"2011","journal-title":"Oper. Res."},{"key":"10.1016\/j.dam.2018.05.032_b3","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1007\/s11590-009-0146-5","article-title":"Approximation algorithms for finding and partitioning unit-disk graphs into co-k-plexes","volume":"4","author":"Balasundaram","year":"2010","journal-title":"Optim. Lett."},{"key":"10.1016\/j.dam.2018.05.032_b4","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/j.dam.2011.08.013","article-title":"On bounded-degree vertex deletion parameterized by treewidth","volume":"160","author":"Betzler","year":"2012","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.dam.2018.05.032_b5","doi-asserted-by":"crossref","first-page":"930","DOI":"10.1007\/s00453-011-9492-7","article-title":"Approximation and tidying\u2013a problem kernel for s-plex cluster vertex deletion","volume":"62","author":"van Bevern","year":"2012","journal-title":"Algorithmica"},{"key":"10.1016\/j.dam.2018.05.032_b6","doi-asserted-by":"crossref","first-page":"1954","DOI":"10.1016\/j.dam.2011.07.009","article-title":"Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms","volume":"159","author":"Bourgeois","year":"2011","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.dam.2018.05.032_b7","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/j.disopt.2015.11.003","article-title":"Fixed-parameter algorithms for vertex cover P3","volume":"19","author":"Chang","year":"2016","journal-title":"Discrete Optim."},{"key":"10.1016\/j.dam.2018.05.032_b8","unstructured":"M.-S. Chang, L.-J. Hung, P.-C. Su, Exact and fixed-parameter algorithms for problems related to 2-plex, in:Proceedings of the 15th International Computer Science and Engineering Conference, ICSEC 2011, 2011, pp. 203\u2013208."},{"key":"10.1016\/j.dam.2018.05.032_b9","unstructured":"M.-S. Chang, L.-J. Hung, P.-C. Su, Measure and conquer: analysis of a branch-and-reduce algorithm for the maximum bounded-degree-1 set problem, in: Proceedings of the 29th Workshop on Combinatorial Mathematics and Computation Theory, 2012, pp. 136\u2013145."},{"key":"10.1016\/j.dam.2018.05.032_b10","doi-asserted-by":"crossref","unstructured":"Z.Z. Chen, M. Fellows, B. Fu, H. Jiang, Y. Liu, L. Wang, B. Zhu, A linear kernel for co-path\/cycle packing, in: Proceedings of the 6th International Conference on Algorithmic Applications in Management, AAIM 2010, in: LNCS, vol. 6124, 90\u2013102.","DOI":"10.1007\/978-3-642-14355-7_10"},{"key":"10.1016\/j.dam.2018.05.032_b11","doi-asserted-by":"crossref","first-page":"439","DOI":"10.4007\/annals.2005.162.439","article-title":"On the hardness of approximating minimum vertex cover","volume":"162","author":"Dinur","year":"2005","journal-title":"Ann. of Math."},{"key":"10.1016\/j.dam.2018.05.032_b12","doi-asserted-by":"crossref","first-page":"1141","DOI":"10.1016\/j.jcss.2010.12.001","article-title":"A generalization of Nemhauser and Trotter\u2019s local optimization theorem","volume":"77","author":"Fellows","year":"2011","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/j.dam.2018.05.032_b13","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/s10878-013-9691-z","article-title":"Randomized parameterized algorithms for P2-packing and co-path packing problems","volume":"29","author":"Feng","year":"2015","journal-title":"J. Combin. Opt."},{"year":"2010","series-title":"Exact Exponential Algorithms","author":"Fomin","key":"10.1016\/j.dam.2018.05.032_b14"},{"key":"10.1016\/j.dam.2018.05.032_b15","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/S0166-218X(98)00035-3","article-title":"A unified approximation algorithm for node-deletion problem","volume":"86","author":"Fujito","year":"1998","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.dam.2018.05.032_b16","series-title":"Proceedings of the 10th International Conference on Algorithms and Complexity, CIAC 2017","first-page":"234","article-title":"Approximating bounded degree deletion via matroid matching","volume":"vol. 10236","author":"Fujito","year":"2017"},{"key":"10.1016\/j.dam.2018.05.032_b17","doi-asserted-by":"crossref","first-page":"1662","DOI":"10.1137\/090767285","article-title":"A more relaxed model for graph-based data clustering: s-plex cluster editing","volume":"24","author":"Guo","year":"2010","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/j.dam.2018.05.032_b18","doi-asserted-by":"crossref","first-page":"7009","DOI":"10.1016\/j.tcs.2011.09.009","article-title":"On computing the minimum 3-path vertex cover and dissociation number of graphs","volume":"412","author":"Kardo\u0161","year":"2011","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/j.dam.2018.05.032_b19","doi-asserted-by":"crossref","first-page":"3640","DOI":"10.1016\/j.tcs.2009.04.021","article-title":"Isolation concepts for efficiently enumerating dense subgraphs","volume":"410","author":"Komusiewicz","year":"2009","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/j.dam.2018.05.032_b20","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/s10878-010-9338-2","article-title":"Combinatorial algorithms for the maximum k-plex problem","volume":"23","author":"McClosky","year":"2012","journal-title":"J. Combin. Opt."},{"key":"10.1016\/j.dam.2018.05.032_b21","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1007\/s10878-011-9391-5","article-title":"Exact combinatorial algorithms and experiments for finding maximum k-plexes","volume":"24","author":"Moser","year":"2012","journal-title":"J. Combin. Opt."},{"key":"10.1016\/j.dam.2018.05.032_b22","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/j.dam.2005.02.029","article-title":"Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover","volume":"152","author":"Nishmura","year":"2005","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.dam.2018.05.032_b23","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/j.ipl.2003.08.005","article-title":"A new approach for approximating node deletion problems","volume":"88","author":"Okun","year":"2003","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/j.dam.2018.05.032_b24","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1080\/0022250X.1978.9989883","article-title":"A graph-theoretic generalization of the clique concept","volume":"6","author":"Seidman","year":"1978","journal-title":"J. Math. Sociol."},{"year":"2008","series-title":"Novel approaches for solving large-scale optimization problems on graphs","author":"Trukhannov","key":"10.1016\/j.dam.2018.05.032_b25"},{"key":"10.1016\/j.dam.2018.05.032_b26","doi-asserted-by":"crossref","first-page":"683","DOI":"10.1016\/j.ipl.2011.04.009","article-title":"A factor 2 approximation algorithm for the vertex cover P3 problem","volume":"111","author":"Tu","year":"2011","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/j.dam.2018.05.032_b27","doi-asserted-by":"crossref","first-page":"7044","DOI":"10.1016\/j.tcs.2011.09.013","article-title":"A primal\u2013dual approximation algorithm for the vertex cover P3 problem","volume":"412","author":"Tu","year":"2011","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/j.dam.2018.05.032_b28","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1016\/j.ipl.2009.12.002","article-title":"An improved kernelization for P2-packing","volume":"110","author":"Wang","year":"2010","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/j.dam.2018.05.032_b29","series-title":"Proceeding of the 21st International Conference on Computing and Combinatorics, COCOON 2015","first-page":"469","article-title":"A measure and conquer approach for the parameterized bounded degree-one vertex deletion","volume":"vol. 9198","author":"Wu","year":"2015"},{"key":"10.1016\/j.dam.2018.05.032_b30","series-title":"Proceedings of Proceedings of the 2007 international conference on Emerging technologies in knowledge discovery and data mining, PAKDD 2007","first-page":"476","article-title":"A parallel algorithm for enumerating all the maximal k-plexes","volume":"vol. 4819","author":"Wu","year":"2007"},{"key":"10.1016\/j.dam.2018.05.032_b31","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/j.tcs.2016.04.043","article-title":"Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems","volume":"657","author":"Xiao","year":"2017","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/j.dam.2018.05.032_b32","series-title":"Proceedings of the 14th Annual Conference on International Theory and Applications of Models of Computation, TAMC 2017","first-page":"654","article-title":"Kernelization and parameterized algorithms for 3-path vertex cover","volume":"vol. 10185","author":"Xiao","year":"2017"},{"key":"10.1016\/j.dam.2018.05.032_b33","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1016\/j.ic.2017.06.001","article-title":"Exact algorithms for maximum independent set","volume":"255","author":"Xiao","year":"2017","journal-title":"Inform. and Comput."},{"key":"10.1016\/j.dam.2018.05.032_b34","doi-asserted-by":"crossref","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","article-title":"Linear degree extractors and the inapproximability of max clique and chromatic number","volume":"3","author":"Zuckerman","year":"2007","journal-title":"Theory Comput."}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X18302932?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X18302932?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,4,5]],"date-time":"2024-04-05T23:32:21Z","timestamp":1712359941000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X18302932"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12]]},"references-count":34,"alternative-id":["S0166218X18302932"],"URL":"https:\/\/doi.org\/10.1016\/j.dam.2018.05.032","relation":{},"ISSN":["0166-218X"],"issn-type":[{"type":"print","value":"0166-218X"}],"subject":[],"published":{"date-parts":[[2018,12]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Moderately exponential time algorithms for the maximum bounded-degree-1 set problem","name":"articletitle","label":"Article Title"},{"value":"Discrete Applied Mathematics","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.dam.2018.05.032","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2018 Elsevier B.V.","name":"copyright","label":"Copyright"}]}}