{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T12:59:44Z","timestamp":1772197184554,"version":"3.50.1"},"reference-count":39,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T00:00:00Z","timestamp":1775001600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T00:00:00Z","timestamp":1775001600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2026,1,23]],"date-time":"2026-01-23T00:00:00Z","timestamp":1769126400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["19K11818"],"award-info":[{"award-number":["19K11818"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2026,4]]},"DOI":"10.1016\/j.tcs.2026.115767","type":"journal-article","created":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T16:12:30Z","timestamp":1769271150000},"page":"115767","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["Comparison of k-creature and t-critter"],"prefix":"10.1016","volume":"1068","author":[{"given":"Kohei","family":"Nomura","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4293-8676","authenticated-orcid":false,"given":"Koichi","family":"Yamazaki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"issue":"1\u20132","key":"10.1016\/j.tcs.2026.115767_bib0001","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","article-title":"A partial k-arboretum of graphs with bounded treewidth","volume":"209","author":"Bodlaender","year":"1998","journal-title":"Theor. Comput. Sci."},{"key":"10.1016\/j.tcs.2026.115767_bib0002","unstructured":"J. Kleinberg, \u00c9. Tardos, Algorithm design, 864 pages. Addison Wesley, ISBN-10."},{"key":"10.1016\/j.tcs.2026.115767_bib0003","series-title":"International Computing and Combinatorics Conference","first-page":"308","article-title":"A linear time algorithm for enumerating all the minimum and minimal separators of a chordal graph","author":"Chandran","year":"2001"},{"issue":"2","key":"10.1016\/j.tcs.2026.115767_bib0004","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1006\/jagm.1998.0936","article-title":"Minimum fill-in on circle and circular-arc graphs","volume":"28","author":"Kloks","year":"1998","journal-title":"J. Algorithms"},{"issue":"12","key":"10.1016\/j.tcs.2026.115767_bib0005","doi-asserted-by":"crossref","first-page":"2611","DOI":"10.1016\/j.dam.2008.08.017","article-title":"On probe permutation graphs","volume":"157","author":"Chandler","year":"2009","journal-title":"Discrete Appl. Math."},{"issue":"5","key":"10.1016\/j.tcs.2026.115767_bib0006","doi-asserted-by":"crossref","first-page":"1","DOI":"10.7155\/jgaa.00008","article-title":"Treewidth and minimum fill-in on d-Trapezoid graphs","volume":"2","author":"Bodlaender","year":"1998","journal-title":"J. Graph Algorithms Appl."},{"issue":"3","key":"10.1016\/j.tcs.2026.115767_bib0007","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1016\/j.disc.2005.12.008","article-title":"Minimal separators in P4-sparse graphs","volume":"306","author":"Nikolopoulos","year":"2006","journal-title":"Discrete Math."},{"issue":"18","key":"10.1016\/j.tcs.2026.115767_bib0008","doi-asserted-by":"crossref","first-page":"2769","DOI":"10.1016\/j.dam.2012.01.025","article-title":"Minimal separators in extended P4-laden graphs","volume":"160","author":"Pedrotti","year":"2012","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"10.1016\/j.tcs.2026.115767_bib0009","article-title":"A polynomial bound on the number of minimal separators and potential maximal cliques in P6-free graphs of bounded clique number","volume":"27","author":"Pilipczuk","year":"2025","journal-title":"Discrete Math. Theoretical Comput. Sci."},{"key":"10.1016\/j.tcs.2026.115767_bib0010","series-title":"Graphs without asteroidal triples","author":"K\u00f6hler","year":"1999"},{"issue":"1","key":"10.1016\/j.tcs.2026.115767_bib0011","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1137\/S0097539799359683","article-title":"Treewidth and minimum fill-in: grouping the minimal separators","volume":"31","author":"Bouchitt\u00e9","year":"2001","journal-title":"SIAM J. Comput."},{"issue":"1\u20132","key":"10.1016\/j.tcs.2026.115767_bib0012","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/S0304-3975(97)83809-1","article-title":"Efficient enumeration of all minimal separators in a graph","volume":"180","author":"Shen","year":"1997","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"10.1016\/j.tcs.2026.115767_bib0013","doi-asserted-by":"crossref","first-page":"605","DOI":"10.1137\/S009753979427087X","article-title":"Listing all minimal separators of a graph","volume":"27","author":"Kloks","year":"1998","journal-title":"SIAM J. Comput."},{"issue":"03","key":"10.1016\/j.tcs.2026.115767_bib0014","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1142\/S0129054100000211","article-title":"Generating all the minimal separators of a graph","volume":"11","author":"Berry","year":"2000","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"15","key":"10.1016\/j.tcs.2026.115767_bib0015","doi-asserted-by":"crossref","first-page":"1660","DOI":"10.1016\/j.dam.2010.05.013","article-title":"Space-optimal, backtracking algorithms to list the minimal vertex separators of a graph","volume":"158","author":"Takata","year":"2010","journal-title":"Discrete Appl. Math."},{"issue":"1\u20132","key":"10.1016\/j.tcs.2026.115767_bib0016","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/S0304-3975(01)00007-X","article-title":"Listing all potential maximal cliques of a graph","volume":"276","author":"Bouchitt\u00e9","year":"2002","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"10.1016\/j.tcs.2026.115767_bib0017","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1137\/140964801","article-title":"Large induced subgraphs via triangulations and CMSO","volume":"44","author":"Fomin","year":"2015","journal-title":"SIAM J. Comput."},{"issue":"1","key":"10.1016\/j.tcs.2026.115767_bib0018","doi-asserted-by":"crossref","first-page":"P1","DOI":"10.37236\/9428","article-title":"Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem","volume":"28","author":"Milani\u010d","year":"2021","journal-title":"Electron. J. Combinatorics"},{"key":"10.1016\/j.tcs.2026.115767_bib0019","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1016\/j.jctb.2021.10.003","article-title":"Graphs with polynomially many minimal separators","volume":"152","author":"Abrishami","year":"2022","journal-title":"J. Combinatorial Theory, Ser. B"},{"issue":"4","key":"10.1016\/j.tcs.2026.115767_bib0020","doi-asserted-by":"crossref","first-page":"3140","DOI":"10.1137\/23M1550530","article-title":"Taming graphs with no large creatures and skinny ladders","volume":"38","author":"Gajarsk\u1ef3","year":"2024","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/j.tcs.2026.115767_bib0021","series-title":"Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","first-page":"3063","article-title":"Graph classes with few minimal separators. i. finite forbidden induced subgraphs","author":"Gartland","year":"2023"},{"key":"10.1016\/j.tcs.2026.115767_bib0022","series-title":"Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","first-page":"3098","article-title":"Graph classes with few minimal separators. II. a dichotomy","author":"Gartland","year":"2023"},{"key":"10.1016\/j.tcs.2026.115767_bib0023","unstructured":"P. Gartland, D. Lokshtanov, Dominated minimal separators are tame (nearly all others are feral), arXiv preprint arXiv: 2007.08761(2020)."},{"key":"10.1016\/j.tcs.2026.115767_bib0024","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1016\/j.tcs.2012.02.038","article-title":"On the structure of linear apex NLC graph grammars","volume":"438","author":"Kim","year":"2012","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"10.1016\/j.tcs.2026.115767_bib0025","doi-asserted-by":"crossref","first-page":"825","DOI":"10.1137\/S0097539701385351","article-title":"On the relationship between clique-width and treewidth","volume":"34","author":"Corneil","year":"2005","journal-title":"SIAM J. Comput."},{"issue":"1","key":"10.1016\/j.tcs.2026.115767_bib0026","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1435375.1435385","article-title":"Approximating rank-width and clique-width quickly","volume":"5","author":"Oum","year":"2008","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"10.1016\/j.tcs.2026.115767_bib0027","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1016\/j.tcs.2019.09.012","article-title":"Mim-width III. graph powers and generalized distance domination problems","volume":"796","author":"Jaffke","year":"2019","journal-title":"Theor. Comput. Sci."},{"key":"10.1016\/j.tcs.2026.115767_bib0028","series-title":"Combinatorics","first-page":"35","article-title":"Cut-set lattices of graphs","volume":"13","author":"Escalante","year":"1974"},{"issue":"4","key":"10.1016\/j.tcs.2026.115767_bib0029","doi-asserted-by":"crossref","first-page":"691","DOI":"10.4153\/CJM-1976-069-6","article-title":"Weak separation lattices of graphs","volume":"28","author":"Sabidussi","year":"1976","journal-title":"Can. J. Math."},{"issue":"1","key":"10.1016\/j.tcs.2026.115767_bib0030","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/S0195-6698(82)80006-1","article-title":"On primitive sets in graphs","volume":"3","author":"Hager","year":"1982","journal-title":"Eur. J. Combinatorics"},{"issue":"2","key":"10.1016\/j.tcs.2026.115767_bib0031","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/S0195-6698(82)80028-0","article-title":"On the lattices of cutsets in finite graphs","volume":"3","author":"Meyer","year":"1982","journal-title":"Eur. J. Combinatorics"},{"issue":"3","key":"10.1016\/j.tcs.2026.115767_bib0032","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/S0195-6698(85)80036-6","article-title":"On maps related to Halin separation lattices","volume":"6","author":"Sabidussi","year":"1985","journal-title":"Eur. J. Combinatorics"},{"key":"10.1016\/j.tcs.2026.115767_bib0033","series-title":"Abhandlungen Aus Dem Mathematischen Seminar Der UniversitAt Hamburg","first-page":"217","article-title":"Lattices of cuts in graphs","volume":"61","author":"Halin","year":"1991"},{"key":"10.1016\/j.tcs.2026.115767_bib0034","series-title":"The Julius Petersen Graph Theory Centennial","first-page":"97","article-title":"Some finiteness results concerning separation in graphs","author":"Halin","year":"1992"},{"key":"10.1016\/j.tcs.2026.115767_bib0035","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/978-94-011-2080-7_10","article-title":"Lattices related to separation in graphs","volume":"411","author":"Halin","year":"1993","journal-title":"Finite Infinite Combinatorics Sets Logic"},{"issue":"1\u20132","key":"10.1016\/j.tcs.2026.115767_bib0036","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/j.dam.2004.02.016","article-title":"Representing a concept lattice by a graph","volume":"144","author":"Berry","year":"2004","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"10.1016\/j.tcs.2026.115767_bib0037","doi-asserted-by":"crossref","first-page":"372","DOI":"10.1016\/j.disc.2005.12.007","article-title":"Listing all the minimal separators of a 3-connected planar graph","volume":"306","author":"Mazoit","year":"2006","journal-title":"Discrete Math"},{"key":"10.1016\/j.tcs.2026.115767_bib0038","unstructured":"M. Chudnovsky, S. Thomass\u00e9, N. Trotignon, K. Vu\u0161kovi\u0107, Maximum independent sets in (pyramid, even hole)-free graphs, arXiv preprint arXiv: 1912.11246(2019)."},{"key":"10.1016\/j.tcs.2026.115767_bib0039","series-title":"Lattices and Ordered Sets","author":"Roman","year":"2008"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397526000265?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397526000265?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T12:05:51Z","timestamp":1772193951000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397526000265"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4]]},"references-count":39,"alternative-id":["S0304397526000265"],"URL":"https:\/\/doi.org\/10.1016\/j.tcs.2026.115767","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2026,4]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Comparison of k-creature and t-critter","name":"articletitle","label":"Article Title"},{"value":"Theoretical Computer Science","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.tcs.2026.115767","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2026 The Author(s). Published by Elsevier B.V.","name":"copyright","label":"Copyright"}],"article-number":"115767"}}