{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:52:09Z","timestamp":1773481929071,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540204527","type":"print"},{"value":"9783540398905","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-39890-5_6","type":"book-chapter","created":{"date-parts":[[2010,9,4]],"date-time":"2010-09-04T01:16:57Z","timestamp":1283563017000},"page":"58-70","source":"Crossref","is-referenced-by-count":26,"title":["The Minimum Degree Heuristic and the Minimal Triangulation Process"],"prefix":"10.1007","author":[{"given":"Anne","family":"Berry","sequence":"first","affiliation":[]},{"given":"Pinar","family":"Heggernes","sequence":"additional","affiliation":[]},{"given":"Genevi\u00e8ve","family":"Simonet","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"6_CR1","doi-asserted-by":"publisher","first-page":"886","DOI":"10.1137\/S0895479894278952","volume":"17","author":"P. Amestoy","year":"1996","unstructured":"Amestoy, P., Davis, T.A., Duff, I.S.: An approximate minimum degree ordering algorithm. SIAM J. Matrix Anal. Appl.\u00a017, 886\u2013905 (1996)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"6_CR2","unstructured":"Berry, A.: D\u00e9sarticulation d\u2019un graphe. PhD Dissertation, LIRMM, Montpellier (December 1998)"},{"key":"6_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-36379-3_1","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"A. Berry","year":"2002","unstructured":"Berry, A., Blair, J.R.S., Heggernes, P.: Maximum Cardinality Search for Computing Minimal Triangulations. In: Ku\u010dera, L. (ed.) WG 2002. LNCS, vol.\u00a02573, pp. 1\u201312. Springer, Heidelberg (2002)"},{"key":"6_CR4","unstructured":"Berry, A., Bordat, J.-P., Heggernes, P., Simonet, G., Villanger, Y.: A widerange algorithm for minimal triangulation from an arbitrary ordering. Reports in Informatics 243, University of Bergen, Norway, 2003, and Research Report 02-200, LIRRM, Montpellier, France. Submitted to Journal of Algorithms (November 2002)"},{"key":"6_CR5","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1016\/S0304-3975(99)00126-7","volume":"250","author":"J.R.S. Blair","year":"2001","unstructured":"Blair, J.R.S., Heggernes, P., Telle, J.A.: A practical algorithm for making filled graphs minimal. Theoretical Computer Science\u00a0250, 124\u2013141 (2001)","journal-title":"Theoretical Computer Science"},{"key":"6_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1007\/BFb0024494","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"E. Dahlhaus","year":"1997","unstructured":"Dahlhaus, E.: Minimal elimination ordering inside a given chordal graph. In: M\u00f6hring, R.H. (ed.) WG 1997. LNCS, vol.\u00a01335, pp. 132\u2013143. Springer, Heidelberg (1997)"},{"key":"6_CR7","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/BF02992776","volume":"25","author":"G.A. Dirac","year":"1961","unstructured":"Dirac, G.A.: On rigid circuit graphs. Anh. Math. Sem. Univ. Hamburg\u00a025, 71\u201376 (1961)","journal-title":"Anh. Math. Sem. Univ. Hamburg"},{"key":"6_CR8","first-page":"835","volume":"15","author":"D.R. Fulkerson","year":"1965","unstructured":"Fulkerson, D.R., Gross, O.A.: Incidence matrices and interval graphs. Pacific. Journal of Math\u00a015, 835\u2013855 (1965)","journal-title":"Journal of Math"},{"key":"6_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/1031001","volume":"31","author":"J.A. George","year":"1989","unstructured":"George, J.A., Liu, J.W.H.: The evolution of the minimum degree ordering algorithm. SIAM Review\u00a031, 1\u201319 (1989)","journal-title":"SIAM Review"},{"key":"6_CR10","doi-asserted-by":"crossref","unstructured":"Heggernes, P., Eisenstat, S., Kumfert, G., Pothen, A.: The computational complexity of the Minimum Degree algorithm. In: Proceedings of 14th Norwegian Computer Science Conference, NIK, University of Troms\u00f8, Norway. Also available as ICASE Report 2001-42, NASA\/CR-2001-211421, NASA Langley Research Center, USA (2001)","DOI":"10.2172\/15002765"},{"key":"6_CR11","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/S0304-3975(96)00206-X","volume":"175","author":"T. Kloks","year":"1997","unstructured":"Kloks, T., Kratsch, D., Spinrad, J.: On treewidth and minimum fill-in of asteroidal triple-free graphs. Theoretical Computer Science\u00a0175, 309\u2013335 (1997)","journal-title":"Theoretical Computer Science"},{"key":"6_CR12","doi-asserted-by":"crossref","first-page":"45","DOI":"10.4064\/fm-51-1-45-64","volume":"51","author":"C.G. Lekkerkerker","year":"1962","unstructured":"Lekkerkerker, C.G., Boland, J.C.: Representation of a finite graph by a set of intervals on the real line. Fund. Math.\u00a051, 45\u201364 (1962)","journal-title":"Fund. Math."},{"key":"6_CR13","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1137\/0909029","volume":"9","author":"J.W.H. Liu","year":"1988","unstructured":"Liu, J.W.H.: Equivalent sparse matrix reorderings by elimination tree rotations. SIAM J. Sci. Stat. Comput.\u00a09, 424\u2013444 (1988)","journal-title":"SIAM J. Sci. Stat. Comput."},{"key":"6_CR14","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1287\/mnsc.3.3.255","volume":"3","author":"H.M. Markowitz","year":"1957","unstructured":"Markowitz, H.M.: The elimination form of the inverse and its application to linear programming. Management Science\u00a03, 255\u2013269 (1957)","journal-title":"Management Science"},{"key":"6_CR15","unstructured":"Matrix Market Web site, http:\/\/math.nist.gov\/MatrixMarket\/"},{"key":"6_CR16","doi-asserted-by":"publisher","first-page":"622","DOI":"10.1016\/0022-247X(76)90182-7","volume":"54","author":"T. Ohtsuki","year":"1976","unstructured":"Ohtsuki, T., Cheung, L.K., Fujisawa, T.: Minimal triangulation of a graph and optimal pivoting order in a sparse matrix. J. Math. Anal. Appl.\u00a054, 622\u2013633 (1976)","journal-title":"J. Math. Anal. Appl."},{"key":"6_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1007\/3-540-60084-1_68","volume-title":"Automata, Languages and Programming","author":"A. Parra","year":"1995","unstructured":"Parra, A., Scheffler, P.: How to use the minimal separators of a graph for its chordal triangulation. In: F\u00fcl\u00f6p, Z., Gecseg, F. (eds.) ICALP 1995. LNCS, vol.\u00a0944, pp. 123\u2013134. Springer, Heidelberg (1995)"},{"key":"6_CR18","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1137\/1003021","volume":"3","author":"S. Parter","year":"1961","unstructured":"Parter, S.: The use of linear graphs in Gauss elimination. SIAM Review\u00a03, 119\u2013130 (1961)","journal-title":"SIAM Review"},{"key":"6_CR19","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1137\/S089547989936443X","volume":"23","author":"B. Peyton","year":"2001","unstructured":"Peyton, B.: Minimal orderings revisited. SIAM J. Matrix Anal. Appl.\u00a023, 271\u2013294 (2001)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"6_CR20","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/B978-1-4832-3187-7.50018-0","volume-title":"Graph Theory and Computing","author":"D.J. Rose","year":"1972","unstructured":"Rose, D.J.: A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations. In: Read, R.C. (ed.) Graph Theory and Computing, pp. 183\u2013217. Academic Press, London (1972)"},{"key":"6_CR21","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"D.J. Rose","year":"1976","unstructured":"Rose, D.J., Tarjan, R.E., Lueker, G.S.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput.\u00a05, 266\u2013283 (1976)","journal-title":"SIAM J. Comput."},{"key":"6_CR22","doi-asserted-by":"publisher","first-page":"1801","DOI":"10.1109\/PROC.1967.6011","volume":"55","author":"W.F. Tinney","year":"1967","unstructured":"Tinney, W.F., Walker, J.W.: Direct solutions of sparse network equations by optimally ordered triangular factorization. Proceedings of the IEEE\u00a055, 1801\u20131809 (1967)","journal-title":"Proceedings of the IEEE"},{"key":"6_CR23","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 J. Alg. Disc. Meth.\u00a02, 77\u201379 (1981)","journal-title":"SIAM J. Alg. Disc. Meth."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-39890-5_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,3]],"date-time":"2019-06-03T13:18:54Z","timestamp":1559567934000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-39890-5_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540204527","9783540398905"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-39890-5_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003]]}}}