{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T04:11:52Z","timestamp":1742962312295,"version":"3.40.3"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319180076"},{"type":"electronic","value":"9783319180083"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","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":[[2015]]},"DOI":"10.1007\/978-3-319-18008-3_4","type":"book-chapter","created":{"date-parts":[[2015,4,15]],"date-time":"2015-04-15T07:32:51Z","timestamp":1429083171000},"page":"47-64","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A Benders Approach to the Minimum Chordal Completion Problem"],"prefix":"10.1007","author":[{"given":"David","family":"Bergman","sequence":"first","affiliation":[]},{"given":"Arvind U.","family":"Raghunathan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,4,16]]},"reference":[{"issue":"3","key":"4_CR1","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1145\/2402.322389","volume":"30","author":"C Beeri","year":"1983","unstructured":"Beeri, C., Fagin, R., Maier, D., Yannakakis, M.: On the desirability of acyclic database schemes. J. ACM 30(3), 479\u2013513 (1983). http:\/\/doi.acm.org\/10.1145\/2402.322389","journal-title":"J. ACM"},{"issue":"1","key":"4_CR2","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/BF01386316","volume":"4","author":"J Benders","year":"1962","unstructured":"Benders, J.: Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik 4(1), 238\u2013252 (1962). http:\/\/dx.doi.org\/10.1007\/BF01386316","journal-title":"Numerische Mathematik"},{"issue":"1","key":"4_CR3","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/j.jalgor.2004.07.001","volume":"58","author":"A Berry","year":"2006","unstructured":"Berry, A., Bordat, J.P., Heggernes, P., Simonet, G., Villanger, Y.: A wide-range algorithm for minimal triangulation from an arbitrary ordering. Journal of Algorithms 58(1), 33\u201366 (2006). http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0196677404001142","journal-title":"Journal of Algorithms"},{"key":"4_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1007\/978-3-540-39890-5_6","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"A Berry","year":"2003","unstructured":"Berry, A., Heggernes, P., Simonet, G.: The minimum degree heuristic and the minimal triangulation process. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol. 2880, pp. 58\u201370. Springer, Heidelberg (2003). http:\/\/www.dx.doi.org\/10.1007\/978-3-540-39890-5_6"},{"issue":"12","key":"4_CR5","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/S0304-3975(99)00126-7","volume":"250","author":"JR Blair","year":"2001","unstructured":"Blair, J.R., Heggernes, P., Telle, J.A.: A practical algorithm for making filled graphs minimal. Theoretical Computer Science 250(12), 125\u2013141 (2001). http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0304397599001267","journal-title":"Theoretical Computer Science"},{"key":"4_CR6","first-page":"1","volume":"11","author":"HL Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybernetica 11, 1\u201323 (1993)","journal-title":"Acta Cybernetica"},{"key":"4_CR7","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Kloks, T., Kratsch, D., Mueller, H.: Treewidth and minimum fill-in on d-trapezoid graphs (1998)","DOI":"10.7155\/jgaa.00008"},{"key":"4_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1007\/978-3-540-92182-0_27","volume-title":"Algorithms and Computation","author":"HL Bodlaender","year":"2008","unstructured":"Bodlaender, H.L., Heggernes, P., Villanger, Y.: Faster parameterized algorithms for Minimum Fill-In. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC 2008. LNCS, vol. 5369, pp. 282\u2013293. Springer, Heidelberg (2008). http:\/\/dx.doi.org\/10.1007\/978-3-540-92182-0_27"},{"key":"4_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/BFb0024492","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"H Broersma","year":"1997","unstructured":"Broersma, H., Dahlhaus, E., Kloks, T.: Algorithms for the treewidth and minimum fill-in of hhd-free graphs. In: M\u00f6hring, R.H. (ed.) WG 1997. LNCS, vol. 1335, pp. 109\u2013117. Springer, Heidelberg (1997). http:\/\/dx.doi.org\/10.1007\/BFb0024492"},{"issue":"2","key":"4_CR10","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/S0304-3975(03)00221-4","volume":"307","author":"LS Chandran","year":"2003","unstructured":"Chandran, L.S., Ibarra, L., Ruskey, F., Sawada, J.: Generating and characterizing the perfect elimination orderings of a chordal graph. Theor. Comput. Sci. 307(2), 303\u2013317 (2003). http:\/\/dx.doi.org\/10.1016\/S0304-3975(03)00221-4","journal-title":"Theor. Comput. Sci."},{"key":"4_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1007\/BFb0009490","volume-title":"Algorithms and Computation","author":"MS Chang","year":"1996","unstructured":"Chang, M.S.: Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs. In: Nagamochi, H., Suri, S., Igarashi, Y., Miyano, S., Asano, T. (eds.) ISAAC 1996. LNCS, vol. 1178, pp. 146\u2013155. Springer, Heidelberg (1996). http:\/\/dx.doi.org\/10.1007\/BFb0009490"},{"issue":"1","key":"4_CR12","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1006\/jctb.1994.1056","volume":"62","author":"F Chung","year":"1994","unstructured":"Chung, F., Mumford, D.: Chordal completions of planar graphs. Journal of Combinatorial Theory, Series B 62(1), 96\u2013106 (1994). http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0095895684710562","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"4_CR13","unstructured":"Fomin, F.V., Villanger, Y.: Subexponential parameterized algorithm for minimum fill-in. In: Proceedings of the Twenty-third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, pp. 1737\u20131746. SIAM (2012), http:\/\/dl.acm.org\/citation.cfm?id=2095116.2095254"},{"issue":"3","key":"4_CR14","doi-asserted-by":"publisher","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"DR Fulkerson","year":"1965","unstructured":"Fulkerson, D.R., Gross, O.A.: Incidence matrices and interval graphs. Pacific Journal of Mathematics 15(3), 835\u2013855 (1965). http:\/\/projecteuclid.org\/euclid.pjm\/1102995572","journal-title":"Pacific Journal of Mathematics"},{"key":"4_CR15","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)"},{"issue":"1","key":"4_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/1031001","volume":"31","author":"A George","year":"1989","unstructured":"George, A., Liu, W.H.: The evolution of the minimum degree ordering algorithm. SIAM Rev. 31(1), 1\u201319 (1989). http:\/\/dx.doi.org\/10.1137\/1031001","journal-title":"SIAM Rev."},{"issue":"3","key":"4_CR17","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1006\/jagm.1995.1047","volume":"19","author":"M Golumbic","year":"1995","unstructured":"Golumbic, M., Kaplan, H., Shamir, R.: Graph sandwich problems. Journal of Algorithms 19(3), 449\u2013473 (1995). http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0196677485710474","journal-title":"Journal of Algorithms"},{"key":"4_CR18","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0024-3795(84)90207-6","volume":"58","author":"R Grone","year":"1984","unstructured":"Grone, R., Johnson, C.R., S\u00e1, E.M., Wolkowicz, H.: Positive definite completions of partial hermitian matrices. Linear Algebra and its Applications 58, 109\u2013124 (1984). http:\/\/www.sciencedirect.com\/science\/article\/pii\/0024379584902076","journal-title":"Linear Algebra and its Applications"},{"issue":"3","key":"4_CR19","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. Discrete Mathematics 306(3), 297\u2013317 (2006). http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0012365X05006060","journal-title":"Discrete Mathematics"},{"key":"4_CR20","doi-asserted-by":"crossref","unstructured":"Heggernes, P., Eisenstat, S.C., Kumfert, G., Pothen, A.: The computational complexity of the minimum degree algorithm (2001)","DOI":"10.2172\/15002765"},{"issue":"1","key":"4_CR21","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/s10107-003-0375-9","volume":"96","author":"J Hooker","year":"2003","unstructured":"Hooker, J., Ottosson, G.: Logic-based benders decomposition. Mathematical Programming 96(1), 33\u201360 (2003). http:\/\/dx.doi.org\/10.1007\/s10107-003-0375-9","journal-title":"Mathematical Programming"},{"key":"4_CR22","first-page":"780","volume":"28","author":"H Kaplan","year":"1994","unstructured":"Kaplan, H., Shamir, R., Tarjan, R.E.: Tractability of parameterized completion problems on chordal and interval graphs: Minimum fill-in and physical mapping (extended abstract). SIAM J. Comput 28, 780\u2013791 (1994)","journal-title":"SIAM J. Comput"},{"issue":"1","key":"4_CR23","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/s10107-010-0402-6","volume":"129","author":"S Kim","year":"2011","unstructured":"Kim, S., Kojima, M., Mevissen, M., Yamashita, M.: Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion. Mathematical Programming 129(1), 33\u201368 (2011). http:\/\/dx.doi.org\/10.1007\/s10107-010-0402-6","journal-title":"Mathematical Programming"},{"issue":"2","key":"4_CR24","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1006\/jagm.1998.0936","volume":"28","author":"T Kloks","year":"1998","unstructured":"Kloks, T., Kratsch, D., Wong, C.: Minimum fill-in on circle and circular-arc graphs. Journal of Algorithms 28(2), 272\u2013289 (1998). http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0196677498909361","journal-title":"Journal of Algorithms"},{"key":"4_CR25","doi-asserted-by":"publisher","first-page":"45","DOI":"10.4064\/fm-51-1-45-64","volume":"51","author":"C Lekkeikerker","year":"1962","unstructured":"Lekkeikerker, C., Boland, J.: Representation of a finite graph by a set of intervals on the real line. Fundamenta Mathematicae 51, 45\u201364 (1962)","journal-title":"Fundamenta Mathematicae"},{"issue":"79","key":"4_CR26","doi-asserted-by":"publisher","first-page":"958","DOI":"10.1016\/j.tcs.2009.10.004","volume":"411","author":"M Mezzini","year":"2010","unstructured":"Mezzini, M., Moscarini, M.: Simple algorithms for minimal triangulation of a graph and backward selection of a decomposable markov network. Theoretical Computer Science 411(79), 958\u2013966 (2010). http:\/\/www.sciencedirect.com\/science\/article\/pii\/S030439750900735X","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"4_CR27","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/s10107-002-0351-9","volume":"95","author":"K Nakata","year":"2003","unstructured":"Nakata, K., Fujisawa, K., Fukuda, M., Kojima, M., Murota, K.: Exploiting sparsity in semidefinite programming via matrix completion ii: implementation and numerical results. Mathematical Programming 95(2), 303\u2013327 (2003). http:\/\/dx.doi.org\/10.1007\/s10107-002-0351-9","journal-title":"Mathematical Programming"},{"key":"4_CR28","unstructured":"Nguyen, T.H., Bui, T.: Graph coloring benchmark instances. http:\/\/www.cs.hbg.psu.edu\/txn131\/graphcoloring.html (accessed: 14 July 2014)"},{"issue":"1","key":"4_CR29","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1137\/S089547989936443X","volume":"23","author":"BW Peyton","year":"2001","unstructured":"Peyton, B.W.: Minimal orderings revisited. SIAM J. Matrix Anal. Appl. 23(1), 271\u2013294 (2001). http:\/\/dx.doi.org\/10.1137\/S089547989936443X","journal-title":"SIAM J. Matrix Anal. Appl."},{"issue":"2","key":"4_CR30","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"D Rose","year":"1976","unstructured":"Rose, D., Tarjan, R., Lueker, G.: Algorithmic aspects of vertex elimination on graphs. SIAM Journal on Computing 5(2), 266\u2013283 (1976). http:\/\/dx.doi.org\/10.1137\/0205021","journal-title":"SIAM Journal on Computing"},{"key":"4_CR31","unstructured":"Rose, D.J.: A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations. In: Graph Theory and Computing, pp. 183\u2013217. Academic Press (1972), http:\/\/www.sciencedirect.com\/science\/article\/pii\/B9781483231877500180"},{"key":"4_CR32","series-title":"Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1007\/978-3-319-03473-7_28","volume-title":"Complex Sciences","author":"N Sokhn","year":"2013","unstructured":"Sokhn, N., Baltensperger, R., Bersier, L.-F., Hennebert, J., Ultes-Nitsche, U.: Identification of chordless cycles in ecological networks. In: Glass, K., Colbaugh, R., Ormerod, P., Tsao, J. (eds.) Complex 2012. LNICST, vol. 126, pp. 316\u2013324. Springer, Heidelberg (2013)"},{"issue":"3","key":"4_CR33","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/S0166-218X(87)80003-3","volume":"18","author":"J Spinrad","year":"1987","unstructured":"Spinrad, J., Brandstdt, A., Stewart, L.: Bipartite permutation graphs. Discrete Applied Mathematics 18(3), 279\u2013292 (1987). http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0166218X87800033","journal-title":"Discrete Applied Mathematics"},{"issue":"3","key":"4_CR34","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1137\/0213035","volume":"13","author":"RE Tarjan","year":"1984","unstructured":"Tarjan, R.E., Yannakakis, M.: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput. 13(3), 566\u2013579 (1984). http:\/\/dx.doi.org\/10.1137\/0213035","journal-title":"SIAM J. Comput."},{"key":"4_CR35","unstructured":"Uno, T., Satoh, H.: An efficient algorithm for enumerating chordless cycles and chordless paths. CoRR abs\/1404.7610 (2014), http:\/\/arxiv.org\/abs\/1404.7610"},{"issue":"1","key":"4_CR36","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1137\/0602010","volume":"2","author":"M Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Computing the minimum fill-in is np-complete. SIAM Journal on Algebraic Discrete Methods 2(1), 77\u201379 (1981)","journal-title":"SIAM Journal on Algebraic Discrete Methods"}],"container-title":["Lecture Notes in Computer Science","Integration of AI and OR Techniques in Constraint Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-18008-3_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,31]],"date-time":"2020-12-31T12:03:04Z","timestamp":1609416184000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-18008-3_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319180076","9783319180083"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-18008-3_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"16 April 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}