{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:19:54Z","timestamp":1740122394666,"version":"3.37.3"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,2,26]],"date-time":"2021-02-26T00:00:00Z","timestamp":1614297600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,2,26]],"date-time":"2021-02-26T00:00:00Z","timestamp":1614297600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100004412","name":"T\u00fcrkiye Bilimler Akademisi","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004412","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2021,4]]},"DOI":"10.1007\/s10878-021-00712-6","type":"journal-article","created":{"date-parts":[[2021,2,26]],"date-time":"2021-02-26T21:02:40Z","timestamp":1614373360000},"page":"710-735","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["The complexity of subtree intersection representation of chordal graphs and linear time chordal graph generation"],"prefix":"10.1007","volume":"41","author":[{"given":"T\u0131naz","family":"Ekim","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mordechai","family":"Shalom","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2357-3584","authenticated-orcid":false,"given":"Oylum","family":"\u015eeker","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,2,26]]},"reference":[{"key":"712_CR1","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1007\/11427186_27","volume-title":"Experimental and efficient algorithms","author":"MI Andreou","year":"2005","unstructured":"Andreou MI, Papadopoulou VG, Spirakis PG, Theodorides B, Xeros A (2005) Generating and radiocoloring families of perfect graphs. In: Nikoletseas SE (ed) Experimental and efficient algorithms. Springer, Berlin, pp 302\u2013314"},{"issue":"7","key":"712_CR2","doi-asserted-by":"publisher","first-page":"899","DOI":"10.1016\/j.dam.2012.11.011","volume":"161","author":"C Bazgan","year":"2013","unstructured":"Bazgan C, Chopin M, Ries B (2013) The firefighter problem with more than one firefighter on trees. Discrete Appl Math 161(7):899\u2013908","journal-title":"Discrete Appl Math"},{"key":"712_CR3","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1016\/j.dam.2014.03.016","volume":"173","author":"R Belmonte","year":"2014","unstructured":"Belmonte R, Heggernes P, van\u2019t Hof P, Rafiey A, Saei R (2014) Graph classes and Ramsey numbers. Discrete Appl Math 173:16\u201327","journal-title":"Discrete Appl Math"},{"key":"712_CR4","unstructured":"Blair JRS, Peyton BW (1993) An introduction to chordal graphs and clique trees. In: Graph theory and sparse matrix computations, IMA Vol. in Math. Appl., vol\u00a056. Springer, Berlin, pp 1\u201327"},{"issue":"3","key":"712_CR5","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1016\/j.tcs.2007.02.045","volume":"379","author":"M Bodirsky","year":"2007","unstructured":"Bodirsky M, Gr\u00f6pl C, Kang M (2007) Generating labeled planar graphs uniformly at random. Theoret Comput Sci 379(3):377\u2013386","journal-title":"Theoret Comput Sci"},{"key":"712_CR6","doi-asserted-by":"crossref","unstructured":"Chaplick S, Zeman P (2017) Combinatorial problems on $$H$$-graphs. arXiv:1706.00575","DOI":"10.1016\/j.endm.2017.06.042"},{"issue":"3","key":"712_CR7","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1016\/j.ejor.2014.12.028","volume":"243","author":"Y Chung","year":"2015","unstructured":"Chung Y, Culus JF, Demange M (2015) Inverse chromatic number problems in interval and permutation graphs. Eur J Oper Res 243(3):763\u2013773","journal-title":"Eur J Oper Res"},{"issue":"2","key":"712_CR8","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1016\/j.ejor.2014.05.011","volume":"240","author":"M Demange","year":"2015","unstructured":"Demange M, Ekim T, Ries B, Tanasescu C (2015) On some applications of the selective graph coloring problem. Eur J Oper Res 240(2):307\u2013314","journal-title":"Eur J Oper Res"},{"key":"712_CR9","unstructured":"Demirci YE, Ekim T, Gimbel J, Y\u0131ld\u0131z MA (2019) Defective Ramsey numbers in graph classes. arXiv:1912.03705"},{"issue":"5","key":"712_CR10","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/j.entcs.2011.06.003","volume":"264","author":"B Dezs","year":"2011","unstructured":"Dezs B, J\u00fcttner A, Kov\u00e1cs P (2011) LEMON\u2014an open source C++ graph template library. Electron Notes Theor Comput Sci 264(5):23\u201345","journal-title":"Electron Notes Theor Comput Sci"},{"key":"712_CR11","volume-title":"Graph theory, Graduate Texts in Mathematics","author":"R Diestel","year":"2012","unstructured":"Diestel R (2012) Graph theory, Graduate Texts in Mathematics, vol 173, 4th edn. Springer, Berlin","edition":"4"},{"key":"712_CR12","doi-asserted-by":"publisher","first-page":"100548","DOI":"10.1016\/j.disopt.2019.06.001","volume":"34","author":"T Ekim","year":"2019","unstructured":"Ekim T, Gimbel J, \u015eeker O (2019a) Small 1-defective Ramsey numbers in perfect graphs. Discrete Optim 34:100548","journal-title":"Discrete Optim"},{"key":"712_CR13","doi-asserted-by":"crossref","unstructured":"Ekim T, Shalom M, \u015eeker O (2019b) The complexity of subtree intersection representation of chordal graphs and linear time chordal graph generation. In: Proceedings of the Special event on analysis of experimental algorithms ($$SEA^2$$ 2019), Kalamata, Greece","DOI":"10.1007\/978-3-030-34029-2_2"},{"key":"712_CR14","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0095-8956(74)90094-X","volume":"16","author":"F Gavril","year":"1974","unstructured":"Gavril F (1974) The intersection graphs of subtrees in trees are exactly the chordal graphs. J Comb Theory 16:47\u201356","journal-title":"J Comb Theory"},{"key":"712_CR15","doi-asserted-by":"crossref","unstructured":"Golovach PA, Heggernes P, Kratsch D, Saei R (2012) An exact algorithm for subset feedback vertex set on chordal graphs. In: International symposium on parameterized and exact computation. Springer, pp 85\u201396","DOI":"10.1007\/978-3-642-33293-7_10"},{"key":"712_CR16","volume-title":"Algorithmic graph theory and perfect graphs, Annals of Discrete Mathematics","author":"MC Golumbic","year":"2004","unstructured":"Golumbic MC (2004) Algorithmic graph theory and perfect graphs, Annals of Discrete Mathematics, vol 57. North-Holland Publishing Co., Amsterdam"},{"key":"712_CR17","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/0020-0190(89)90070-7","volume":"31","author":"CW Ho","year":"1989","unstructured":"Ho CW, Lee RCT (1989) Computing clique trees and computing perfect elimination schemes in parallel. Inf Process Lett 31:61\u201368","journal-title":"Inf Process Lett"},{"issue":"1","key":"712_CR18","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/s10479-007-0190-4","volume":"157","author":"L Markenzon","year":"2008","unstructured":"Markenzon L, Vernet O, Araujo LH (2008) Two methods for the generation of chordal graph. Ann Oper Res 157(1):47\u201360","journal-title":"Ann Oper Res"},{"issue":"3","key":"712_CR19","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1016\/j.tcs.2005.10.008","volume":"351","author":"D Marx","year":"2006","unstructured":"Marx D (2006) Parameterized coloring problems on chordal graphs. Theor Comput Sci 351(3):407\u2013424","journal-title":"Theor Comput Sci"},{"key":"712_CR20","doi-asserted-by":"crossref","unstructured":"McKee TA, McMorris FR (1999) Topics in intersection graph theory. SIAM monographs on Discrete Mathematics and Applications","DOI":"10.1137\/1.9780898719802"},{"key":"712_CR21","volume-title":"Probabilistic reasoning in intelligent systems: networks of plausible inference","author":"J Pearl","year":"2014","unstructured":"Pearl J (2014) Probabilistic reasoning in intelligent systems: networks of plausible inference. Morgan Kaufmann, Burlington"},{"key":"712_CR22","first-page":"2","volume":"10","author":"SV Pemmaraju","year":"2005","unstructured":"Pemmaraju SV, Penumatcha S, Raman R (2005) Approximating interval coloring and max-coloring in chordal graphs. J Exp Algorithms 10:2\u20138","journal-title":"J Exp Algorithms"},{"key":"712_CR23","doi-asserted-by":"crossref","unstructured":"Rose DJ (1972) A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equation. In: Graph theory and computing, pp 183\u2013217","DOI":"10.1016\/B978-1-4832-3187-7.50018-0"},{"issue":"2","key":"712_CR24","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"DJ Rose","year":"1976","unstructured":"Rose DJ, Tarjan RE, Lueker GS (1976) Algorithmic aspects of vertex elimination on graphs. SIAM J Comput 5(2):266\u2013283","journal-title":"SIAM J Comput"},{"key":"712_CR25","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1016\/j.jda.2011.11.001","volume":"10","author":"T Saitoh","year":"2012","unstructured":"Saitoh T, Otachi Y, Yamanaka K, Uehara R (2012) Random generation and enumeration of bipartite permutation graphs. J Discrete Algorithms 10:84\u201397","journal-title":"J Discrete Algorithms"},{"key":"712_CR26","doi-asserted-by":"crossref","unstructured":"\u015eeker O, Heggernes P, Ekim T, Ta\u015fk\u0131n ZC (2017) Linear-time generation of random chordal graphs. In: 10th international conference on algorithms and complexity, CIAC (2017) vol 10236. Lecture Notes in Computer Science. Springer, Berlin, pp 442\u2013453","DOI":"10.1007\/978-3-319-57586-5_37"},{"key":"712_CR27","unstructured":"\u015eeker O, Heggernes P, Ekim T, Ta\u015fk\u0131n ZC (2018) Generation of random chordal graphs using subtrees of a tree. arXiv preprint arXiv:1810.13326"},{"issue":"2","key":"712_CR28","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1002\/net.21850","volume":"73","author":"O \u015eeker","year":"2019","unstructured":"\u015eeker O, Ekim T, Ta\u015fk\u0131n ZC (2019) A decomposition approach to solve the selective graph coloring problem in some perfect graph families. Networks 73(2):145\u2013169","journal-title":"Networks"},{"key":"712_CR29","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2020.09.017","author":"O \u015eeker","year":"2020","unstructured":"\u015eeker O, Ekim T, Ta\u015fk\u0131n ZC (2020) An exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs. Eur J Oper Res. https:\/\/doi.org\/10.1016\/j.ejor.2020.09.017","journal-title":"Eur J Oper Res"},{"key":"712_CR30","first-page":"235","volume-title":"Generating graphs uniformly at random","year":"1990","unstructured":"Tinhofer G, Mayr E, Noltemeier H, Syslo MM (eds) (1990) Generating graphs uniformly at random. Springer, Vienna, pp 235\u2013255"},{"key":"712_CR31","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1016\/j.tcs.2019.04.017","volume":"806","author":"K Yamazaki","year":"2020","unstructured":"Yamazaki K, Saitoh T, Kiyomi M, Uehara R (2020) Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs. Theoret Comput Sci 806:310\u2013322","journal-title":"Theoret Comput Sci"},{"issue":"2\u20133","key":"712_CR32","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/s10589-005-3060-5","volume":"33","author":"EA Y\u0131ld\u0131r\u0131m","year":"2006","unstructured":"Y\u0131ld\u0131r\u0131m EA, Fan-Orzechowski X (2006) On extracting maximum stable sets in perfect graphs using Lov\u00e1sz\u2019s theta function. Comput Optim Appl 33(2\u20133):229\u2013247","journal-title":"Comput Optim Appl"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00712-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-021-00712-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00712-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,10]],"date-time":"2021-03-10T08:35:05Z","timestamp":1615365305000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-021-00712-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,26]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,4]]}},"alternative-id":["712"],"URL":"https:\/\/doi.org\/10.1007\/s10878-021-00712-6","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2021,2,26]]},"assertion":[{"value":"8 February 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 February 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Complaince with ethical standards"}},{"value":"The authors have no conflicts of interest to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}