{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:34:48Z","timestamp":1787330088727,"version":"build-2736575974"},"reference-count":33,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"name":"Center of Excellence DEWS"},{"DOI":"10.13039\/100009112","name":"Istituto Nazionale di Alta Matematica \"Francesco Severi\"","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100009112","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003407","name":"Ministero dell'Istruzione, dell'Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Matrix Anal. Appl."],"published-print":{"date-parts":[[2019,1]]},"abstract":"<jats:p>A novel algorithmic approach is presented for the problem of partitioning a connected undirected weighted graph under constraints such as cardinality or membership requirements or must-link and cannot-link constraints. Such constrained problems can be NP-hard combinatorial optimization problems. They are restated as matrix nearness problems for the weight matrix of the graph, where the objective is to minimize the distance between the given weight matrix and perturbed weight matrices for which a functional of an eigenvalue and eigenvector of the graph Laplacian takes its minimal value. A key element in the numerical solution of these matrix nearness problems is the use of a gradient system of matrix differential equations for the functional.<\/jats:p>","DOI":"10.1137\/17m1160987","type":"journal-article","created":{"date-parts":[[2019,1,3]],"date-time":"2019-01-03T11:04:53Z","timestamp":1546513493000},"page":"1-22","source":"Crossref","is-referenced-by-count":8,"title":["Constrained Graph Partitioning via Matrix Differential Equations"],"prefix":"10.1137","volume":"40","author":[{"given":"Eleonora","family":"Andreotti","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dominik","family":"Edelmann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nicola","family":"Guglielmi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christian","family":"Lubich","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2019,1,3]]},"reference":[{"key":"atypb1","unstructured":"S. Basu, A. Banerjee, and R. J. Mooney,\n                      Semi-supervised clustering by seeding\n                      , in Proceedings of the Nineteenth International Conference on Machine Learning (ICML '02), Morgan Kaufmann, San Francisco, CA, 2002, pp. 27-34."},{"key":"atypb2","first-page":"59","author":"Basu S.","year":"2004","journal-title":"New York"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"S. Basu, I. Davidson, and K. Wagstaff,\n                      Constrained Clustering: Advances in Algorithms, Theory, and Applications\n                      , Chapman and Hall\/CRC, Boca Raton, FL, 2008.","DOI":"10.1201\/9781584889977"},{"key":"atypb4","first-page":"11","author":"Bilenko M.","year":"2004","journal-title":"New York"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2005.05.036"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(03)00358-5"},{"key":"atypb7","first-page":"624","author":"B\u00fchler T.","year":"2013","journal-title":"GA"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"F. R. K. Chung,\n                      Spectral Graph Theory\n                      , AMS, Providence, RI, 1997.","DOI":"10.1090\/cbms\/092"},{"key":"atypb9","unstructured":"D. Edelmann,\n                      Graph Partitioning Using Differential Equations\n                      , Master's thesis, University of T\u00fcbingen, 2017."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.21136\/CMJ.1973.101168"},{"key":"atypb11","first-page":"48","author":"Filippov A. F.","year":"1988","journal-title":"New York"},{"key":"atypb12","unstructured":"R. Fletcher,\n                      Practical Methods of Optimization\n                      , John Wiley & Sons, New York, 2013."},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.122653799"},{"key":"atypb14","unstructured":"G. H. Golub and C. F. Van Loan,\n                      Matrix Computations\n                      , 3rd edition, The Johns Hopkins University Press, Baltimore, MD, 1996."},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-014-0637-x"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1137\/100817851"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1137\/16M1105840"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1137\/16M1079026"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/j.cam.2006.04.026"},{"key":"atypb20","unstructured":"S. D. Kamvar, D. Klein, and C. D. Manning,\n                      Spectral learning\n                      , in Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI '03), Morgan Kaufmann, San Francisco, CA, 2003, pp. 561-566."},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"T. Kato,\n                      Perturbation Theory for Linear Operators\n                      , Springer, New York, 1995.","DOI":"10.1007\/978-3-642-66282-9"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"R. B. Lehoucq, D. C. Sorensen, and C. Yang,\n                      ARPACK Users' Guide: Solution of Large-Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods\n                      , SIAM, Philadelphia, 1998.","DOI":"10.1137\/1.9780898719628"},{"key":"atypb23","first-page":"421","author":"Li Z.","year":"2009","journal-title":"Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), Miami, FL"},{"key":"atypb24","first-page":"2339","volume":"13","author":"Mahoney M. W.","year":"2012","journal-title":"J. Mach. Learn. Res."},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1137\/0725041"},{"key":"atypb26","unstructured":"Y. Saad,\n                      Numerical Methods for Large Eigenvalue Problems\n                      , Manchester University Press, Manchester, UK, 1992."},{"key":"atypb27","doi-asserted-by":"crossref","unstructured":"D. Spielman,\n                      Spectral graph theory and its application\n                      , in Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, 2007, pp. 29-38.","DOI":"10.1109\/FOCS.2007.56"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263872"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1007\/s11222-007-9033-z"},{"key":"atypb30","unstructured":"K. Wagstaff, C. Cardie, S. Rogers, and S. Schr\u00f6dl,\n                      Constrained k-means clustering with background knowledge\n                      , in Proceedings of the 18th International Conference on Machine Learning (ICML '01), Morgan Kaufmann, San Francisco, CA, 2001, pp. 577-584."},{"key":"atypb31","first-page":"563","author":"Wang X.","year":"2010","journal-title":"New York"},{"key":"atypb32","first-page":"2866","author":"Xu L.","year":"2009","journal-title":"Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1086\/jar.33.4.3629752"}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1160987","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:47:14Z","timestamp":1787327234000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1160987"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["10.1137\/17M1160987"],"URL":"https:\/\/doi.org\/10.1137\/17m1160987","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1]]}}}