{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T15:09:22Z","timestamp":1770304162233,"version":"3.49.0"},"reference-count":22,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2026,3,1]],"date-time":"2026-03-01T00:00:00Z","timestamp":1772323200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2026,3,1]],"date-time":"2026-03-01T00:00:00Z","timestamp":1772323200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2025,12,18]],"date-time":"2025-12-18T00:00:00Z","timestamp":1766016000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2026,3]]},"DOI":"10.1016\/j.tcs.2025.115706","type":"journal-article","created":{"date-parts":[[2025,12,21]],"date-time":"2025-12-21T15:34:53Z","timestamp":1766331293000},"page":"115706","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["Finding proportionally dense subgraphs of maximum size in degree-constrained graphs"],"prefix":"10.1016","volume":"1065","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4702-673X","authenticated-orcid":false,"given":"Narmina","family":"Baghirova","sequence":"first","affiliation":[]},{"given":"Antoine","family":"Castillon","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/j.tcs.2025.115706_bib0001","first-page":"25","article-title":"Proportionally dense subgraph of maximum size: complexity and approximation","volume":"270","author":"Bazgan","year":"2019","journal-title":"J. Combinator. Algo. Inf. Computat. Sci."},{"issue":"Suppl 7","key":"10.1016\/j.tcs.2025.115706_bib0002","doi-asserted-by":"crossref","first-page":"670","DOI":"10.1186\/s12864-018-5027-9","article-title":"Discovering large conserved functional components in global network alignment by graph matching","volume":"19","author":"Zhu","year":"2018","journal-title":"BMC Genomics"},{"issue":"3","key":"10.1016\/j.tcs.2025.115706_bib0003","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1016\/j.mathsocsci.2013.07.002","article-title":"A general view on computing communities","volume":"66","author":"Olsen","year":"2013","journal-title":"Math. Soc. Sci."},{"issue":"6","key":"10.1016\/j.tcs.2025.115706_bib0004","doi-asserted-by":"crossref","first-page":"1890","DOI":"10.1007\/s00453-017-0283-7","article-title":"Structural and algorithmic properties of 2-community structures","volume":"80","author":"Bazgan","year":"2018","journal-title":"Algorithmica"},{"key":"10.1016\/j.tcs.2025.115706_bib0005","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1007\/s004530010050","article-title":"The dense k-Subgraph problem","volume":"29","author":"Feige","year":"2001","journal-title":"Algorithmica"},{"issue":"1","key":"10.1016\/j.tcs.2025.115706_bib0006","doi-asserted-by":"crossref","DOI":"10.3390\/a9010021","article-title":"Multivariate algorithmics for finding cohesive subnetworks","volume":"9","author":"Komusiewicz","year":"2016","journal-title":"Algorithms"},{"key":"10.1016\/j.tcs.2025.115706_bib0007","first-page":"23","article-title":"On connected two communities","volume":"135","author":"Estivill-Castro","year":"2013"},{"key":"10.1016\/j.tcs.2025.115706_bib0008","doi-asserted-by":"crossref","DOI":"10.1016\/j.ipl.2019.105877","article-title":"Graphs without a partition into two proportionally dense subgraphs","volume":"155","author":"Bazgan","year":"2020","journal-title":"Inf. Process. Lett."},{"key":"10.1016\/j.tcs.2025.115706_bib0009","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/j.dam.2024.07.033","article-title":"Finding k-community structures in special graph classes","volume":"359","author":"Baghirova","year":"2024","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.tcs.2025.115706_bib0010","series-title":"33rd International Symposium on Algorithms and Computation (ISAAC 2022)","first-page":"31:1","article-title":"Locally checkable problems parameterized by clique-width","volume":"248","author":"Baghirova","year":"2022"},{"key":"10.1016\/j.tcs.2025.115706_bib0011","series-title":"Graph Theory","author":"Diestel","year":"2005"},{"key":"10.1016\/j.tcs.2025.115706_bib0012","article-title":"Treewidth","volume":"842","author":"Kloks","year":"1994","journal-title":"Lect. Notes Comput. Sci."},{"key":"10.1016\/j.tcs.2025.115706_bib0013","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/j.dam.2022.01.019","article-title":"A new approach on locally checkable problems","volume":"314","author":"Bonomo-Braberman","year":"2022","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.tcs.2025.115706_bib0014","doi-asserted-by":"crossref","DOI":"10.1016\/j.dam.2019.07.010","article-title":"Proportionally dense subgraph of maximum size: complexity and approximation","volume":"270","author":"Bazgan","year":"2019","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.tcs.2025.115706_bib0015","series-title":"Community Detection: Computational Complexity and Approximation","author":"Pontoizeau","year":"2018"},{"issue":"20","key":"10.1016\/j.tcs.2025.115706_bib0016","doi-asserted-by":"crossref","first-page":"2742","DOI":"10.1016\/j.disc.2010.05.028","article-title":"Maximum independent sets in 3- and 4-regular hamiltonian graphs","volume":"310","author":"Fleischner","year":"2010","journal-title":"Discrete Math."},{"key":"10.1016\/j.tcs.2025.115706_bib0017","article-title":"Bipartite Graphs and their Applications","volume":"131","author":"Asratian","year":"1998"},{"issue":"1","key":"10.1016\/j.tcs.2025.115706_bib0018","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1006\/jctb.2000.2026","article-title":"Face covers and the genus problem for apex graphs","volume":"82","author":"Mohar","year":"2001","journal-title":"J. Combinat. Theory Ser. B"},{"key":"10.1016\/j.tcs.2025.115706_bib0019","series-title":"Mathematical Foundations of Computer Science 2008","first-page":"96","article-title":"The maximum independent set problem in planar graphs","author":"Alekseev","year":"2008"},{"key":"10.1016\/j.tcs.2025.115706_bib0020","series-title":"New Width Parameters of Graphs","author":"Vatshelle","year":"2012"},{"key":"10.1016\/j.tcs.2025.115706_bib0021","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/j.tcs.2022.01.022","article-title":"Parameterized complexity of satisfactory partition problem","volume":"907","author":"Gaikwad","year":"2022","journal-title":"Theor. Comput. Sci."},{"issue":"8","key":"10.1016\/j.tcs.2025.115706_bib0022","doi-asserted-by":"crossref","first-page":"1236","DOI":"10.1016\/j.dam.2005.10.014","article-title":"The satisfactory partition problem","volume":"154","author":"Bazgan","year":"2006","journal-title":"Discrete Appl. Math."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397525006437?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397525006437?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T00:49:31Z","timestamp":1770252571000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397525006437"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3]]},"references-count":22,"alternative-id":["S0304397525006437"],"URL":"https:\/\/doi.org\/10.1016\/j.tcs.2025.115706","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2026,3]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Finding proportionally dense subgraphs of maximum size in degree-constrained graphs","name":"articletitle","label":"Article Title"},{"value":"Theoretical Computer Science","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.tcs.2025.115706","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2025 The Author(s). Published by Elsevier B.V.","name":"copyright","label":"Copyright"}],"article-number":"115706"}}