{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T14:30:18Z","timestamp":1783780218464,"version":"3.55.0"},"reference-count":31,"publisher":"EDP Sciences","issue":"2","license":[{"start":{"date-parts":[[2022,3,25]],"date-time":"2022-03-25T00:00:00Z","timestamp":1648166400000},"content-version":"vor","delay-in-days":24,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004412","name":"T\u00fcrkiye Bilimler Akademisi","doi-asserted-by":"publisher","award":["GEBIP"],"award-info":[{"award-number":["GEBIP"]}],"id":[{"id":"10.13039\/501100004412","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2022,2,12]]},"published-print":{"date-parts":[[2022,3]]},"abstract":"<jats:p>Chordal graphs form one of the most studied graph classes. Several graph problems that are NP-hard in general become solvable in polynomial time on chordal graphs, whereas many others remain NP-hard. For a large group of problems among the latter, approximation algorithms, parameterized algorithms, and algorithms with moderately exponential or sub-exponential running time have been designed. Chordal graphs have also gained increasing interest during the recent years in the area of enumeration algorithms. Being able to test these algorithms on instances of chordal graphs is crucial for understanding the concepts of tractability of hard problems on graph classes. Unfortunately, only few published papers give algorithms for generating chordal graphs. Even in these papers, only very few methods aim for generating a large variety of chordal graphs. Surprisingly, none of these methods is directly based on the \u201cintersection of subtrees of a tree\u201d characterization of chordal graphs. In this paper, we give an algorithm for generating chordal graphs, based on the characterization that a graph is chordal if and only if it is the intersection graph of subtrees of a tree. Upon generating a random host tree, we give and test various methods that generate subtrees of the host tree. We compare our methods to one another and to existing ones for generating chordal graphs. Our experiments show that one of our methods is able to generate the largest variety of chordal graphs in terms of maximal clique sizes. Moreover, two of our subtree generation methods result in an overall complexity of our generation algorithm that is the best possible time complexity for a method generating the entire node set of subtrees in an \u201cintersection of subtrees of a tree\u201d representation. The instances corresponding to the results presented in this paper, and also a set of relatively small-sized instances are made available online.<\/jats:p>","DOI":"10.1051\/ro\/2022027","type":"journal-article","created":{"date-parts":[[2022,2,15]],"date-time":"2022-02-15T08:56:20Z","timestamp":1644915380000},"page":"565-582","source":"Crossref","is-referenced-by-count":1,"title":["Generation of random chordal graphs using subtrees of a tree"],"prefix":"10.1051","volume":"56","author":[{"given":"Oylum","family":"\u015eeker","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pinar","family":"Heggernes","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tinaz","family":"Ekim","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Z. Caner","family":"Ta\u015fk\u0131n","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"250","published-online":{"date-parts":[[2022,3,25]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"739","DOI":"10.1016\/j.ipl.2016.07.002","volume":"116","author":"Abu-Khzam","year":"2016","journal-title":"Inf. Process. Lett."},{"key":"R2","doi-asserted-by":"crossref","unstructured":"Andreou M.I., Papadopoulou V.G., Spirakis P.G., Theodorides B. and Xeros A., Generating and radiocoloring families of perfect graphs. In: Experimental and Efficient Algorithms. Springer (2005) 302\u2013314.","DOI":"10.1007\/11427186_27"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"Blair J.R.S. and Peyton B.W., An introduction to chordal graphs and clique trees. In: Graph Theory and Sparse Matrix Computations. IMA in Math. Appl., Vol. 56. Springer (1993) 1\u201327.","DOI":"10.1007\/978-1-4613-8369-7_1"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"Bougeret M., Bousquet N., Giroudeau R. and Watrigant R., Parameterized complexity of the sparsest k-subgraph problem in chordal graphs. SOFSEM. Springer (2014) 150\u2013161.","DOI":"10.1007\/978-3-319-04298-5_14"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt A., Le V.B. and Spinrad J., Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications (1999).","DOI":"10.1137\/1.9780898719796"},{"key":"R6","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/0012-365X(74)90002-8","volume":"9","author":"Buneman","year":"1974","journal-title":"Disc. Math."},{"key":"R7","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/BF02992776","volume":"25","author":"Dirac","year":"1961","journal-title":"Ann. Math. Sem. Univ. Hamburg"},{"key":"R8","doi-asserted-by":"crossref","first-page":"710","DOI":"10.1007\/s10878-021-00712-6","volume":"41","author":"Ekim","year":"2021","journal-title":"J. Comb. Optim."},{"key":"R9","doi-asserted-by":"crossref","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"Fulkerson","year":"1965","journal-title":"Pac. J. Math."},{"key":"R10","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1137\/0201013","volume":"1","author":"Gavril","year":"1972","journal-title":"SIAM J. Comp."},{"key":"R11","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0095-8956(74)90094-X","volume":"16","author":"Gavril","year":"1974","journal-title":"J. Comb. Th. B"},{"key":"R12","first-page":"7","volume":"26","author":"Golovach","year":"2014","journal-title":"J. Disc. Alg."},{"key":"R13","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/j.tcs.2016.03.026","volume":"630","author":"Golovach","year":"2016","journal-title":"Theor. Comput. Sci."},{"key":"R14","doi-asserted-by":"crossref","unstructured":"Golumbic M.C., Algorithmic Graph Theory and Perfect Graphs. Ann. Disc. Math. Vol. 57. Elsevier (2004).","DOI":"10.1016\/S0167-5060(04)80051-7"},{"key":"R15","unstructured":"Hajnal A. and Sur\u00e1nyi J., \u00dcber die Aufl\u00f6sung von Graphen in vollst\u00e4ndige Teilgraphen. Ann. Univ. Sci. Budapest (1958) 113\u2013121."},{"key":"R16","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/BF02401834","volume":"37","author":"Hardy","year":"1914","journal-title":"Acta Math."},{"key":"R17","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/j.disc.2005.12.003","volume":"306","author":"Heggernes","year":"2006","journal-title":"Disc. Math."},{"key":"R18","unstructured":"Knuth D.E., The Art of Computer Programming: Seminumerical Algorithms. Vol. 2, Chapter 4. Addison-Wesley (1969)."},{"key":"R19","unstructured":"Loksthanov D., Dagstuhl Seminar 14071 \u201cGraph Modification Problems (2014)."},{"key":"R20","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1145\/322123.322125","volume":"26","author":"Lueker","year":"1979","journal-title":"JACM"},{"key":"R21","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/s10479-007-0190-4","volume":"157","author":"Markenzon","year":"2008","journal-title":"Ann. Oper. Res."},{"key":"R22","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1016\/j.tcs.2005.10.008","volume":"351","author":"Marx","year":"2006","journal-title":"Theor. Comput. Sci."},{"key":"R23","doi-asserted-by":"crossref","unstructured":"Misra N., Panolan F., Rai A., Raman V. and Saurabh S., Parameterized Algorithms for Max Colorable Induced Subgraph Problem on Perfect Graphs, LNCS, vol. 8165 Springer (2013) 370\u2013381.","DOI":"10.1007\/978-3-642-45043-3_32"},{"key":"R24","unstructured":"Pearl J., Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann (2014)."},{"key":"R25","first-page":"2","volume":"10","author":"Pemmaraju","year":"2005","journal-title":"J. Exp. Alg."},{"key":"R26","doi-asserted-by":"crossref","unstructured":"Rodionov A.S. and Choo H., On generating random network structures: trees. International Conference on Computational Science. LNCS, Vol. 2658. Springer (2003) 879\u2013887.","DOI":"10.1007\/3-540-44862-4_95"},{"key":"R27","first-page":"217","volume":"183","author":"Rose","year":"1972","journal-title":"Graph Theory Comput."},{"key":"R28","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"Rose","year":"1976","journal-title":"SIAM J. Comp."},{"key":"R29","doi-asserted-by":"crossref","unstructured":"\u015eeker O., Heggernes P., Ekim T. and Ta\u015fkn Z.C., Linear-time generation of random chordal graphs. In: Algorithms and Complexity: 10th International Conference, CIAC 2017, LNCS, Vol. 10236. Springer (2017) 442\u2013453.","DOI":"10.1007\/978-3-319-57586-5_37"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"Spinrad J.P., Efficient Graph Representations. Fields Institute Monograph Series. Vol. 19. AMS (2003).","DOI":"10.1090\/fim\/019"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"Tarjan R.E., Data Structures and Network Algorithms. SIAM, Philadelphia, (1983).","DOI":"10.1137\/1.9781611970265"}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2022027\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,25]],"date-time":"2022-03-25T08:57:10Z","timestamp":1648198630000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2022027"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3]]},"references-count":31,"journal-issue":{"issue":"2"},"alternative-id":["ro200200"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2022027","relation":{},"ISSN":["0399-0559","2804-7303"],"issn-type":[{"value":"0399-0559","type":"print"},{"value":"2804-7303","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3]]}}}