{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T14:27:00Z","timestamp":1759847220519,"version":"3.40.3"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319575858"},{"type":"electronic","value":"9783319575865"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-57586-5_37","type":"book-chapter","created":{"date-parts":[[2017,4,13]],"date-time":"2017-04-13T15:23:34Z","timestamp":1492097014000},"page":"442-453","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Linear-Time Generation of Random Chordal Graphs"],"prefix":"10.1007","author":[{"given":"Oylum","family":"\u015eeker","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pinar","family":"Heggernes","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"T\u0131naz","family":"Ekim","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Z. Caner","family":"Ta\u015fk\u0131n","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,4,14]]},"reference":[{"issue":"12","key":"37_CR1","doi-asserted-by":"publisher","first-page":"739","DOI":"10.1016\/j.ipl.2016.07.002","volume":"116","author":"F Abu-Khzam","year":"2016","unstructured":"Abu-Khzam, F., Heggernes, P.: Enumerating minimal dominating sets in chordal graphs. Inf. Process. Lett. 116(12), 739\u2013743 (2016)","journal-title":"Inf. Process. Lett."},{"key":"37_CR2","series-title":"Lecture Notes in Computer Science","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, M.I., Papadopoulou, V.G., Spirakis, P.G., Theodorides, B., Xeros, A.: Generating and radiocoloring families of perfect graphs. In: Nikoletseas, S.E. (ed.) WEA 2005. LNCS, vol. 3503, pp. 302\u2013314. Springer, Heidelberg (2005). doi:10.1007\/11427186_27"},{"key":"37_CR3","series-title":"The IMA Volumes in Mathematics and Its Applications","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-1-4613-8369-7_1","volume-title":"Graph Theory, Sparse Matrix Computations","author":"JRS Blair","year":"1993","unstructured":"Blair, J.R.S., Peyton, B.W.: An introduction to chordal graphs, clique trees. In: George, A., Gilbert, J.R., Liu, J.W.H. (eds.) Graph Theory, Sparse Matrix Computations. The IMA Volumes in Mathematics and Its Applications, vol. 56, pp. 1\u201329. Springer, New York (1993)"},{"key":"37_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1007\/978-3-319-04298-5_14","volume-title":"SOFSEM 2014: Theory and Practice of Computer Science","author":"M Bougeret","year":"2014","unstructured":"Bougeret, M., Bousquet, N., Giroudeau, R., Watrigant, R.: Parameterized complexity of the sparsest k-subgraph problem in chordal graphs. In: Geffert, V., Preneel, B., Rovan, B., \u0160tuller, J., Tjoa, A.M. (eds.) SOFSEM 2014. LNCS, vol. 8327, pp. 150\u2013161. Springer, Cham (2014). doi:10.1007\/978-3-319-04298-5_14"},{"issue":"3","key":"37_CR5","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0012-365X(74)90002-8","volume":"9","author":"P Buneman","year":"1974","unstructured":"Buneman, P.: A characterisation of rigid circuit graphs. Disc. Math. 9(3), 205\u2013212 (1974)","journal-title":"Disc. Math."},{"key":"37_CR6","series-title":"SIAM Monographs on Discrete Mathematics and Applications","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey","author":"A Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.: Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia (1999)"},{"key":"37_CR7","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/BF02992776","volume":"25","author":"GA Dirac","year":"1961","unstructured":"Dirac, G.A.: On rigid circuit graphs. Ann. Math. Semin. Univ. Hamburg 25, 71\u201376 (1961)","journal-title":"Ann. Math. Semin. Univ. Hamburg"},{"issue":"3","key":"37_CR8","doi-asserted-by":"publisher","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"D Fulkerson","year":"1965","unstructured":"Fulkerson, D., Gross, O.: Incidence matrices and interval graphs. Pac. J. Math. 15(3), 835\u2013855 (1965)","journal-title":"Pac. J. Math."},{"issue":"2","key":"37_CR9","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1137\/0201013","volume":"1","author":"F Gavril","year":"1972","unstructured":"Gavril, F.: Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM J. Comput. 1(2), 180\u2013187 (1972)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"37_CR10","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.: The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Comb. Theory Ser. B 16(1), 47\u201356 (1974)","journal-title":"J. Comb. Theory Ser. B"},{"key":"37_CR11","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/j.tcs.2016.03.026","volume":"630","author":"P Golovach","year":"2016","unstructured":"Golovach, P., Heggernes, P., Kratsch, D.: Enumerating minimal connected dominating sets in graphs of bounded chordality. Theor. Comput. Sci. 630, 63\u201375 (2016)","journal-title":"Theor. Comput. Sci."},{"key":"37_CR12","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1016\/j.jda.2013.09.005","volume":"26","author":"P Golovach","year":"2014","unstructured":"Golovach, P., Heggernes, P., Kratsch, D., Saei, R.: An exact algorithm for subset feedback vertex set on chordal graphs. J. Discret. Algorithms 26, 7\u201315 (2014)","journal-title":"J. Discret. Algorithms"},{"key":"37_CR13","series-title":"Annals of Discrete Mathematics","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"MC Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Annals of Discrete Mathematics. Elsevier, Amsterdam (2004)"},{"key":"37_CR14","first-page":"113","volume":"1","author":"A Hajnal","year":"1958","unstructured":"Hajnal, A., Sur\u00e1nyi, J.: \u00dcber die Ausfl\u00f6sung von Graphen in vollst\u00e4ndige Teilgraphen. Ann. Univ. Sci. Bp. 1, 113\u2013121 (1958)","journal-title":"Ann. Univ. Sci. Bp."},{"issue":"3","key":"37_CR15","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/j.disc.2005.12.003","volume":"306","author":"P Heggernes","year":"2006","unstructured":"Heggernes, P.: Minimal triangulations of graphs: a survey. Discret. Math. 306(3), 297\u2013317 (2006)","journal-title":"Discret. Math."},{"key":"37_CR16","unstructured":"Loksthanov, D.: Dagstuhl Seminar 14071 \u201cGraph Modification Problems\u201d (2014)"},{"issue":"2","key":"37_CR17","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1145\/322123.322125","volume":"26","author":"GS Lueker","year":"1979","unstructured":"Lueker, G.S., Booth, K.S.: A linear time algorithm for deciding interval graph isomorphism. JACM 26(2), 183\u2013195 (1979)","journal-title":"JACM"},{"issue":"1","key":"37_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, L.H.: Two methods for the generation of chordal graphs. Ann. Oper. Res. 157(1), 47\u201360 (2008)","journal-title":"Ann. Oper. Res."},{"issue":"3","key":"37_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.: Parameterized coloring problems on chordal graphs. Theor. Comput. Sci. 351(3), 407\u2013424 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"37_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"370","DOI":"10.1007\/978-3-642-45043-3_32","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"N Misra","year":"2013","unstructured":"Misra, N., Panolan, F., Rai, A., Raman, V., Saurabh, S.: Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs. In: Brandst\u00e4dt, A., Jansen, K., Reischuk, R. (eds.) WG 2013. LNCS, vol. 8165, pp. 370\u2013381. Springer, Heidelberg (2013). doi:10.1007\/978-3-642-45043-3_32"},{"key":"37_CR21","volume-title":"Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference","author":"J Pearl","year":"2014","unstructured":"Pearl, J.: Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, Burlington (2014)"},{"key":"37_CR22","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/1064546.1180619","volume":"10","author":"SV Pemmaraju","year":"2005","unstructured":"Pemmaraju, S.V., Penumatcha, S., Raman, R.: Approximating interval coloring and max-coloring in chordal graphs. J. Exp. Algorithmics 10, 2\u20138 (2005)","journal-title":"J. Exp. Algorithmics"},{"key":"37_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"879","DOI":"10.1007\/3-540-44862-4_95","volume-title":"Computational Science \u2014 ICCS 2003","author":"AS Rodionov","year":"2003","unstructured":"Rodionov, A.S., Choo, H.: On generating random network structures: trees. In: Sloot, P.M.A., Abramson, D., Bogdanov, A.V., Gorbachev, Y.E., Dongarra, J.J., Zomaya, A.Y. (eds.) ICCS 2003. LNCS, vol. 2658, pp. 879\u2013887. Springer, Heidelberg (2003). doi:10.1007\/3-540-44862-4_95"},{"key":"37_CR24","first-page":"217","volume":"183","author":"DJ Rose","year":"1972","unstructured":"Rose, D.J.: A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations. Graph Theory Comput. 183, 217 (1972)","journal-title":"Graph Theory Comput."},{"issue":"2","key":"37_CR25","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"DJ Rose","year":"1976","unstructured":"Rose, D.J., Tarjan, R.E., Lueker, G.S.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. 5(2), 266\u2013283 (1976)","journal-title":"SIAM J. Comput."},{"key":"37_CR26","series-title":"Fields Institute Monograph Series","volume-title":"Efficient Graph Representations","author":"JP Spinrad","year":"2003","unstructured":"Spinrad, J.P.: Efficient Graph Representations. Fields Institute Monograph Series, vol. 19. AMS, Providence (2003)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-57586-5_37","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T14:51:08Z","timestamp":1710341468000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-57586-5_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319575858","9783319575865"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-57586-5_37","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"14 April 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithms and Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Athens","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Greece","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 May 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 May 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ciac2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.corelab.ntua.gr\/ciac2017\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}