{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T08:44:21Z","timestamp":1774946661264,"version":"3.50.1"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2013,2,16]],"date-time":"2013-02-16T00:00:00Z","timestamp":1360972800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2014,6]]},"DOI":"10.1007\/s10107-013-0648-x","type":"journal-article","created":{"date-parts":[[2013,2,15]],"date-time":"2013-02-15T02:56:04Z","timestamp":1360896964000},"page":"291-325","source":"Crossref","is-referenced-by-count":23,"title":["A new graph parameter related to bounded rank positive semidefinite matrix completions"],"prefix":"10.1007","volume":"145","author":[{"given":"Monique","family":"Laurent","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antonios","family":"Varvitsiotis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,2,16]]},"reference":[{"issue":"1","key":"648_CR1","doi-asserted-by":"crossref","first-page":"53","DOI":"10.4171\/PM\/1881","volume":"68","author":"AY Alfakih","year":"2011","unstructured":"Alfakih, A.Y., Anjos, M.F., Picciali, V., Wolkowicz, H.: Euclidean distance matrices, semidefinite programming and sensor network localization. Portugaliae Mathematica 68(1), 53\u2013102 (2011)","journal-title":"Portugaliae Mathematica"},{"key":"648_CR2","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1023\/A:1008655427845","volume":"12","author":"AY Alfakih","year":"1999","unstructured":"Alfakih, A.Y., Khandani, A., Wolkowicz, H.: Solving Euclidean distance matrix completion problems via semidefinite programming. Comput. Optim. Appl. 12, 13\u201330 (1999)","journal-title":"Comput. Optim. Appl."},{"issue":"1","key":"648_CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0012-365X(90)90292-P","volume":"8","author":"S Arnborg","year":"1990","unstructured":"Arnborg, S., Proskurowski, A., Corneil, D.G.: Forbidden minors characterization of partial 3-trees. Discret. Math. 8(1), 1\u201319 (1990)","journal-title":"Discret. Math."},{"key":"648_CR4","doi-asserted-by":"crossref","unstructured":"Avidor, A., Zwick, U.: Rounding two and three dimensional solutions of the SDP relaxation of MAX CUT. In: Chekuri C. et al. (eds.) APPROX and RANDOM 2005, LNCS 3624, pp. 14\u201325 (2005)","DOI":"10.1007\/11538462_2"},{"issue":"3","key":"648_CR5","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/0167-6377(83)90016-0","volume":"2","author":"F Barahona","year":"1983","unstructured":"Barahona, F.: The max-cut problem on graphs not contractible to $K_5$. Oper. Res. Lett. 2(3), 107\u2013111 (1983)","journal-title":"Oper. Res. Lett."},{"key":"648_CR6","doi-asserted-by":"crossref","unstructured":"Barrett, W.W., Johnson, C.R., Tarazaga, P.: The real positive definite completion problem: cycle completability. Mem. Am. Math. Soc. 584, 69 (1996)","DOI":"10.1090\/memo\/0584"},{"issue":"1","key":"648_CR7","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/s004540010074","volume":"25","author":"A Barvinok","year":"2001","unstructured":"Barvinok, A.: A remark on the rank of positive semidefinite matrices subject to affine constraints. Discret. Comput. Geom. 25(1), 23\u201331 (2001)","journal-title":"Discret. Comput. Geom."},{"key":"648_CR8","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1007\/s00454-006-1285-4","volume":"37","author":"M Belk","year":"2007","unstructured":"Belk, M.: Realizability of graphs in three dimensions. Discret. Comput. Geom. 37, 139\u2013162 (2007)","journal-title":"Discret. Comput. Geom."},{"key":"648_CR9","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/s00454-006-1284-5","volume":"37","author":"M Belk","year":"2007","unstructured":"Belk, M., Connelly, R.: Realizability of graphs. Discret. Comput. Geom. 37, 125\u2013137 (2007)","journal-title":"Discret. Comput. Geom."},{"key":"648_CR10","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/s10107-002-0356-4","volume":"94","author":"S Burer","year":"2002","unstructured":"Burer, S., Monteiro, R.D.C., Zhang, Y.: Maximum stable sets formulations and heuristics based on continuous optimization. Math. Program. 94, 137\u2013166 (2002)","journal-title":"Math. Program."},{"issue":"2","key":"648_CR11","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1006\/jctb.1998.1834","volume":"74","author":"Y Colin de Verdi\u00e8re","year":"1998","unstructured":"Colin de Verdi\u00e8re, Y.: Multiplicities of eigenvalues and tree-width of graphs. J. Comb. Theory Ser. B 74(2), 121\u2013146 (1998)","journal-title":"J. Comb. Theory Ser. B"},{"key":"648_CR12","doi-asserted-by":"crossref","DOI":"10.1007\/b105286","volume-title":"Aspects of Semidefinite Programming - Interior Point Algorithms and Selected Applications","author":"E Klerk de","year":"2002","unstructured":"de Klerk, E.: Aspects of Semidefinite Programming - Interior Point Algorithms and Selected Applications. Kluwer, Dordrecht (2002)"},{"key":"648_CR13","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-04295-9","volume-title":"Geometry of Cuts and Metrics","author":"M Deza","year":"1997","unstructured":"Deza, M., Laurent, M.: Geometry of Cuts and Metrics. Springer, Berlin (1997)"},{"issue":"2","key":"648_CR14","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/0022-247X(65)90125-3","volume":"10","author":"RJ Duffin","year":"1965","unstructured":"Duffin, R.J.: Topology of series-parallel networks. J. Math. Anal. Appl. 10(2), 303\u2013313 (1965)","journal-title":"J. Math. Anal. Appl."},{"key":"648_CR15","doi-asserted-by":"crossref","unstructured":"Eisenberg-Nagy, M., Laurent, M., Varvitsiotis, A.: Complexity of the positive semidefinite matrix completion problem with a rank constraint. (2012, Preprint). Available at: arXiv:1203.6602v2","DOI":"10.1007\/978-3-319-00200-2_7"},{"key":"648_CR16","doi-asserted-by":"crossref","first-page":"558","DOI":"10.1016\/j.laa.2007.05.036","volume":"426","author":"SM Fallat","year":"2007","unstructured":"Fallat, S.M., Hogben, L.: The minimum rank of symmetric matrices described by a graph: a survey. Linear Algebra Appl. 426, 558\u2013582 (2007)","journal-title":"Linear Algebra Appl."},{"key":"648_CR17","unstructured":"Fallat, S.M., Hogben, L.: Variants on the minimum rank problem: a survey II. Preprint. Available at: arXiv:1102.5142v1 (2011)"},{"issue":"1","key":"648_CR18","doi-asserted-by":"crossref","first-page":"472","DOI":"10.1137\/050639430","volume":"19","author":"F G\u00f6ring","year":"2008","unstructured":"G\u00f6ring, F., Helmberg, C., Wappler, M.: Embedded in the shadow of the separator. SIAM J. Optim. 19(1), 472\u2013501 (2008)","journal-title":"SIAM J. Optim."},{"issue":"4","key":"648_CR19","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1002\/jgt.20502","volume":"66","author":"F G\u00f6ring","year":"2011","unstructured":"G\u00f6ring, F., Helmberg, C., Wappler, M.: The rotational dimension of a graph. J. Graph Theory 66(4), 283\u2013302 (2011)","journal-title":"J. Graph Theory"},{"issue":"1\u20132","key":"648_CR20","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/s10107-010-0344-z","volume":"131","author":"F G\u00f6ring","year":"2012","unstructured":"G\u00f6ring, F., Helmberg, C., Reiss, S.: Graph realizations associated with minimizing the maximum eigenvalue of the Laplacian. Math. Program. 131(1\u20132), 95\u2013111 (2012)","journal-title":"Math. Program."},{"key":"648_CR21","doi-asserted-by":"crossref","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 Appl. 58, 109\u2013124 (1984)","journal-title":"Linear Algebra Appl."},{"key":"648_CR22","doi-asserted-by":"crossref","first-page":"2560","DOI":"10.1016\/j.laa.2007.12.004","volume":"428","author":"L Hogben","year":"2008","unstructured":"Hogben, L.: Orthogonal representations, minimum rank, and graph complements. Linear Algebra Appl. 428, 2560\u20132568 (2008)","journal-title":"Linear Algebra Appl."},{"key":"648_CR23","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511810817","volume-title":"Matrix Analysis","author":"RA Horn","year":"1985","unstructured":"Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (1985)"},{"key":"648_CR24","doi-asserted-by":"crossref","first-page":"879","DOI":"10.1007\/978-1-4614-0769-0_30","volume-title":"Handbook on Semidefinite, Conic and Polynomial Optimization","author":"N Krislock","year":"2012","unstructured":"Krislock, N., Wolkowicz, H.: Euclidean distance matrices and applications. In: Anjos, M.F., Lasserre, J.B. (eds.) Handbook on Semidefinite, Conic and Polynomial Optimization, pp. 879\u2013914. Springer, Berlin (2012)"},{"key":"648_CR25","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1016\/0024-3795(95)00741-5","volume":"252","author":"M Laurent","year":"1997","unstructured":"Laurent, M.: The real positive semidefinite completion problem for series parallel graphs. Linear Algebra Appl. 252, 347\u2013366 (1997)","journal-title":"Linear Algebra Appl."},{"key":"648_CR26","first-page":"221","volume-title":"The Encyclopedia of Optimization","author":"M Laurent","year":"2001","unstructured":"Laurent, M.: Matrix completion problems. In: Floudas, C.A., Pardalos, P.M. (eds.) The Encyclopedia of Optimization, vol. III, pp. 221\u2013229. Kluwer, Dordrecht (2001)"},{"key":"648_CR27","doi-asserted-by":"crossref","first-page":"874","DOI":"10.1137\/S0895479899352689","volume":"22","author":"M Laurent","year":"2000","unstructured":"Laurent, M.: Polynomial instances of the positive semidefinite and euclidean distance matrix completion problems. SIAM J. Matrix Anal. Appl. 22, 874\u2013894 (2000)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"648_CR28","doi-asserted-by":"crossref","unstructured":"Laurent, M., Varvitsiotis, A.: The Gram dimension of a graph. In: Proceedings of the 2nd International Symposium on Combinatorial Optimization, LNCS 7422, pp. 356\u2013367 (2012)","DOI":"10.1007\/978-3-642-32147-4_32"},{"key":"648_CR29","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"IT\u201325","author":"L Lov\u00e1sz","year":"1979","unstructured":"Lov\u00e1sz, L.: On the Shannon capacity of a graph. IEEE Trans. Inf. Theory IT\u201325, 1\u20137 (1979)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"648_CR30","unstructured":"Lov\u00e1sz, L., Vesztergombi, K.: Geometric representations of graphs. In: Hal\u00e1sz, G., et al. (eds.) Paul Erd\u00f6s and his Mathematics, pp. 471\u2013498. Bolyai Society Mathematical Studies (2002)"},{"key":"648_CR31","unstructured":"Man-Cho So, A.: A semidefinite programming approach to the graph realization problem. PhD thesis, University of Stanford (2007)"},{"key":"648_CR32","doi-asserted-by":"crossref","unstructured":"Man-Cho So, A., Ye, Y.: A semidefinite programming approach to tensegrity theory and realizability of graphs. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 766\u2013775. (2006)","DOI":"10.1145\/1109557.1109641"},{"issue":"2","key":"648_CR33","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/s10589-007-9131-z","volume":"43","author":"J Nie","year":"2009","unstructured":"Nie, J.: Sum of squares method for sensor network localization. Comput. Optim. Appl. 43(2), 151\u2013179 (2009)","journal-title":"Comput. Optim. Appl."},{"issue":"3","key":"648_CR34","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1137\/070697835","volume":"52","author":"B Recht","year":"2010","unstructured":"Recht, B., Fazel, M., Parrilo, P.A.: Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Rev. 52(3), 471\u2013501 (2010)","journal-title":"SIAM Rev."},{"issue":"2","key":"648_CR35","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/j.jctb.2004.08.001","volume":"92","author":"N Robertson","year":"2004","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XX. Wagner\u2019s conjecture. J. Comb. Theory Ser. B 92(2), 325\u2013357 (2004)","journal-title":"J. Comb. Theory Ser. B"},{"key":"648_CR36","doi-asserted-by":"crossref","DOI":"10.1515\/9781400873173","volume-title":"Convex Analysis","author":"RT Rockafellar","year":"1970","unstructured":"Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970)"},{"key":"648_CR37","unstructured":"van der Holst, H.: Topological and Spectral Graph Characterizations. Ph.D. thesis, University of Amsterdam (1996)"},{"issue":"4","key":"648_CR38","doi-asserted-by":"crossref","first-page":"633","DOI":"10.1007\/s00493-003-0038-8","volume":"23","author":"H Holst van der","year":"2003","unstructured":"van der Holst, H.: Two tree-width-like graph Invariants. Combinatorica 23(4), 633\u2013651 (2003)","journal-title":"Combinatorica"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-013-0648-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-013-0648-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-013-0648-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T21:22:25Z","timestamp":1745961745000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-013-0648-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,2,16]]},"references-count":38,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2014,6]]}},"alternative-id":["648"],"URL":"https:\/\/doi.org\/10.1007\/s10107-013-0648-x","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,2,16]]}}}