{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T13:30:16Z","timestamp":1760707816610},"reference-count":54,"publisher":"Springer Science and Business Media LLC","issue":"1-3","license":[{"start":{"date-parts":[[1997,10,1]],"date-time":"1997-10-01T00:00:00Z","timestamp":875664000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Programming"],"published-print":{"date-parts":[[1997,10]]},"DOI":"10.1007\/bf02614320","type":"journal-article","created":{"date-parts":[[2007,4,28]],"date-time":"2007-04-28T00:34:10Z","timestamp":1177720450000},"page":"255-283","source":"Crossref","is-referenced-by-count":14,"title":["Cuts, matrix completions and graph rigidity"],"prefix":"10.1007","volume":"79","author":[{"given":"Monique","family":"Laurent","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF02614320_CR1","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1137\/0805002","volume":"5","author":"F. Alizadeh","year":"1995","unstructured":"F. Alizadeh, Interior point methods in semidefinite programming with applications in combinatorial optimization,SIAM Journal on Optimization 5 (1995) 13\u201351.","journal-title":"SIAM Journal on Optimization"},{"key":"BF02614320_CR2","doi-asserted-by":"crossref","first-page":"646","DOI":"10.1137\/S0895479893249757","volume":"16","author":"M. Bakonyi","year":"1995","unstructured":"M. Bakonyi and C.R. Johnson, The Euclidian distance matrix completion problem,SIAM Journal on Matrix Analysis and Applications 16 (1995) 646\u2013654.","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"BF02614320_CR3","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/BF01580600","volume":"60","author":"F. Barahona","year":"1993","unstructured":"F. Barahona, On cuts and matchings in planar graphs,Mathematical Programming 60 (1993) 53\u201368.","journal-title":"Mathematical Programming"},{"key":"BF02614320_CR4","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF02592023","volume":"36","author":"F. Barahona","year":"1986","unstructured":"F. Barahona and A.R. Mahjoub, On the cut polytope,Mathematical Programming 36 (1986) 157\u2013173.","journal-title":"Mathematical Programming"},{"key":"BF02614320_CR5","unstructured":"W.W. Barrett, C.R. Johnson and R. Loewy, The real positive definite completion problem: Cycle completability,Memoirs of the American Mathematical Society 584 (1996) 69 pp."},{"key":"BF02614320_CR6","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0024-3795(93)90234-F","volume":"192","author":"W. Barrett","year":"1993","unstructured":"W. Barrett, C.R. Johnson and P. Tarazaga, The real positive definite completion problem for a simple cycle,Linear Algebra and its Applications 192 (1993) 3\u201331.","journal-title":"Linear Algebra and its Applications"},{"key":"BF02614320_CR7","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/BF02574037","volume":"13","author":"A.I. Barvinok","year":"1995","unstructured":"A.I. Barvinok, Problems of distance geometry and convex properties of quadratic maps,Discrete and Computational Geometry 13 (1995) 189\u2013202.","journal-title":"Discrete and Computational Geometry"},{"key":"BF02614320_CR8","volume-title":"Theory and Applications of Distance Geometry","author":"L.M. Blumenthal","year":"1953","unstructured":"L.M. Blumenthal,Theory and Applications of Distance Geometry (Oxford University Press, Oxford, 1953; Chelsea, New York, 2nd ed., 1970)."},{"key":"BF02614320_CR9","doi-asserted-by":"crossref","first-page":"27","DOI":"10.2140\/pjm.1980.90.27","volume":"90","author":"E.D. Bolker","year":"1980","unstructured":"E.D. Bolker and B. Roth, When is a bipartite graph a rigid framework?Pacific Journal of Mathematics 90 (1980) 27\u201344.","journal-title":"Pacific Journal of Mathematics"},{"key":"BF02614320_CR10","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/BF01420337","volume":"244","author":"J.P.R. Christensen","year":"1979","unstructured":"J.P.R. Christensen and J. Vesterstr\u00f8m, A note on extreme positive definite matrices,Mathematische Annalen 244 (1979) 65\u201368.","journal-title":"Mathematische Annalen"},{"key":"BF02614320_CR11","volume-title":"Distance Geometry and Molecular Conformation","author":"G.M. Crippen","year":"1988","unstructured":"G.M. Crippen and T.F. Havel,Distance Geometry and Molecular Conformation (Research Studies Press, Taunton, Somerset, UK, 1988)."},{"key":"BF02614320_CR12","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":"M. Deza and M. Laurent,Geometry of Cuts and Metrics, Algorithms and Combinatorics, Vol. 15 (Springer, Berlin, 1997)."},{"key":"BF02614320_CR13","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/BF02992776","volume":"25","author":"G.A. Dirac","year":"1961","unstructured":"G.A. Dirac, On rigid circuit graphs,Abhandlungen aus dem Mathematischen Seminar der Universit\u00e4t Hamburg 25 (1961) 71\u201376.","journal-title":"Abhandlungen aus dem Mathematischen Seminar der Universit\u00e4t Hamburg"},{"key":"BF02614320_CR14","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/0022-247X(65)90125-3","volume":"10","author":"R. Duffin","year":"1965","unstructured":"R. Duffin, Topology of series-parallel networks,Journal of Mathematical Analysis and Applications 10 (1965) 303\u2013318.","journal-title":"Journal of Mathematical Analysis and Applications"},{"key":"BF02614320_CR15","doi-asserted-by":"crossref","first-page":"67","DOI":"10.6028\/jres.069B.004","volume":"69","author":"J. Edmonds","year":"1965","unstructured":"J. Edmonds, Minimum partition of a matroid into independent subsets,Journal of Research of the National Bureau of Standards B 69 (1965) 67\u201372.","journal-title":"Journal of Research of the National Bureau of Standards B"},{"key":"BF02614320_CR16","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/BF02063286","volume":"10","author":"L. Fejes T\u00f3th","year":"1959","unstructured":"L. Fejes T\u00f3th, \u00dcber eine Punktverteilung auf der Kugel,Acta Mathematica Academiae Scientiarum Hungaricae 10 (1959) 13\u201319.","journal-title":"Acta Mathematica Academiae Scientiarum Hungaricae"},{"key":"BF02614320_CR17","doi-asserted-by":"crossref","unstructured":"H.N. Gabow and H.H. Westermann, Forests, frames and games: Algorithms for matroid sums and applications, in:Proc. 20th Ann. ACM Symp. on the Theory of Computing (1988) 407\u2013421.","DOI":"10.1145\/62212.62252"},{"key":"BF02614320_CR18","unstructured":"M.X. Goemans and D.P. Williamson, 0.878-approximation algorithms for MAX CUT and MAX 2SAT, in:Proc. 26th Ann. ACM Symp. on the Theory of Computing (1994) 422\u2013431."},{"key":"BF02614320_CR19","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0024-3795(84)90207-6","volume":"58","author":"R. Grone","year":"1984","unstructured":"R. Grone, C.R. Johnson, E.M. S\u00e1 and H. Wolkowicz, Positive definite completions of partial hermitian matrices,Linear Algebra and its Applications 58 (1984) 109\u2013124.","journal-title":"Linear Algebra and its Applications"},{"key":"BF02614320_CR20","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/0024-3795(90)90006-X","volume":"134","author":"R. Grone","year":"1990","unstructured":"R. Grone, S. Pierce and W. Watkins, Extremal correlation matrices,Linear Algebra and its Applications 134 (1990) 63\u201370.","journal-title":"Linear Algebra and its Applications"},{"key":"BF02614320_CR21","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M. Gr\u00f6tschel","year":"1981","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization,Combinatorica 1 (1981) 169\u2013197.","journal-title":"Combinatorica"},{"key":"BF02614320_CR22","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M. Gr\u00f6tschel","year":"1988","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz and A. Schrijver,Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics, Vol. 2 (Springer, Berlin, 1988)."},{"key":"BF02614320_CR23","volume-title":"The molecule problem: Determining conformation from pairwise distances","author":"B. Hendrickson","year":"1990","unstructured":"B. Hendrickson, The molecule problem: Determining conformation from pairwise distances, Ph.D. Thesis, Tech. Rept. 90\u20131159, Dept. of Computer Science, Cornell University, Ithaca, NY, 1990."},{"key":"BF02614320_CR24","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1137\/0221008","volume":"21","author":"B. Hendrickson","year":"1992","unstructured":"B. Hendrickson, Conditions for unique graph realizations,SIAM Journal on Computing 21 (1992) 65\u201384.","journal-title":"SIAM Journal on Computing"},{"key":"BF02614320_CR25","doi-asserted-by":"crossref","first-page":"835","DOI":"10.1137\/0805040","volume":"5","author":"B. Hendrickson","year":"1995","unstructured":"B. Hendrickson, The molecule problem: Exploiting structure in global optimization,SIAM Journal on Optimization 5 (1995) 835\u2013857.","journal-title":"SIAM Journal on Optimization"},{"key":"BF02614320_CR26","series-title":"Proceedings of Symposia in Applied Mathematics","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1090\/psapm\/040\/1059486","volume-title":"Matrix Theory and Applications","author":"C.R. Johnson","year":"1990","unstructured":"C.R. Johnson, Matrix completion problems: a survey, in: C.R. Johnson, ed.,Matrix Theory and Applications, Proceedings of Symposia in Applied Mathematics, Vol. 40 (American Mathematical Society, Providence, RI, 1990) 171\u2013198."},{"key":"BF02614320_CR27","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1080\/03081089508818392","volume":"39","author":"C.R. Johnson","year":"1995","unstructured":"C.R. Johnson, C. Jones and B. Kroschel, The distance matrix completion problem: Cycle completability,Linear and Multilinear Algebra 39 (1995) 195\u2013207.","journal-title":"Linear and Multilinear Algebra"},{"key":"BF02614320_CR28","unstructured":"C.R. Johnson, B. Kroschel and H. Wolkowicz, An interior-point method for approximate positive semidefinite completions, CORR Rept. 95-11, University of Waterloo, 1995, to appear inComputational Optimization and Applications."},{"key":"BF02614320_CR29","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0012-365X(95)00107-8","volume":"159","author":"C.R. Johnson","year":"1996","unstructured":"C.R. Johnson and T.A. McKee, Structural conditions for cycle completable graphs,Discrete Mathematics 159 (1996) 155\u2013160.","journal-title":"Discrete Mathematics"},{"key":"BF02614320_CR30","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R.M. Karp","year":"1972","unstructured":"R.M. Karp, Reducibility among combinatorial problems, in: R.E. Miller and J.W. Thatcher, eds.,Complexity of Computer Computations (Plenum Press, New York, 1972) 85\u2013103."},{"key":"BF02614320_CR31","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1007\/BF01534980","volume":"4","author":"G. Laman","year":"1970","unstructured":"G. Laman, On graphs and rigidity of plane skeletal structures,Journal of Engineering Mathematics 4 (1970) 331\u2013340.","journal-title":"Journal of Engineering Mathematics"},{"key":"BF02614320_CR32","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1016\/0024-3795(95)00741-5","volume":"252","author":"M. Laurent","year":"1997","unstructured":"M. Laurent, The real positive semidefinite completion problem for series-parallel graphs,Linear Algebra and its Applications 252 (1997) 347\u2013366.","journal-title":"Linear Algebra and its Applications"},{"key":"BF02614320_CR33","doi-asserted-by":"crossref","unstructured":"M. Laurent, A connection between positive semidefinite and Euclidean distance matrix completion problems,Linear Algebra and its Applications (1997), to appear.","DOI":"10.1090\/fic\/018\/05"},{"key":"BF02614320_CR34","volume-title":"Topics in Semidefinite and Interior-Point Methods","author":"M. Laurent","year":"1997","unstructured":"M. Laurent, A tour d\u2019horizon on positive semidefinite and Euclidean distance matrix completion problems, in: P. Pardalos and H. Wolkowicz, eds.,Topics in Semidefinite and Interior-Point Methods, The Fields Institute for Research in Mathematical Science, Communications Series, Providence, RI (1997), to appear."},{"key":"BF02614320_CR35","volume-title":"Annotated Bibliographies in Combinatorial Optimization","author":"M. Laurent","year":"1997","unstructured":"M. Laurent, Max-cut problem, in: M. Dell\u2019Amico, F. Maffioli and S. Martello, eds.,Annotated Bibliographies in Combinatorial Optimization (John Wiley & Sons, New York, 1997), to appear."},{"key":"BF02614320_CR36","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1016\/0024-3795(95)00271-R","volume":"223\u2013224","author":"M. Laurent","year":"1995","unstructured":"M. Laurent and S. Poljak, On a positive semidefinite relaxation of the cut polytope,Linear Algebra and its Applications 223\u2013224 (1995) 439\u2013461.","journal-title":"Linear Algebra and its Applications"},{"key":"BF02614320_CR37","first-page":"285","volume-title":"Handbook of Statistics","author":"J. Leeuw de","year":"1982","unstructured":"J. de Leeuw and W. Heiser, Theory of multidimensional scaling, in: P.R. Krishnaiah and L.N. Kanal, eds,Handbook of Statistics, Vol. 2 (North-Holland, Amsterdam, 1982) 285\u2013316."},{"key":"BF02614320_CR38","doi-asserted-by":"crossref","first-page":"903","DOI":"10.1137\/S0895479892240683","volume":"15","author":"Chi-Kwong Li","year":"1994","unstructured":"Chi-Kwong Li and Bit-Shun Tam, A note on extreme correlation matrices,SIAM Journal on Matrix Analysis and its Appplications 15 (1994) 903\u2013908.","journal-title":"SIAM Journal on Matrix Analysis and its Appplications"},{"key":"BF02614320_CR39","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1007\/BF03220000","volume":"253","author":"R. Loewy","year":"1980","unstructured":"R. Loewy, Extreme points of a convex subset of the cone of positive semidefinite matrices,Mathematische Annalen 253 (1980) 227\u2013232.","journal-title":"Mathematische Annalen"},{"key":"BF02614320_CR40","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1137\/0603009","volume":"3","author":"L. Lov\u00e1sz","year":"1982","unstructured":"L. Lov\u00e1sz and Y. Yemini, On generic rigidity in the plane,SIAM Journal on Algebraic and Discrete Methods 3 (1982) 91\u201398.","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"key":"BF02614320_CR41","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970791","volume-title":"Interior Point Polynomial Algorithms in Convex Programming: Theory and Algorithms","author":"Y.E. Nesterov","year":"1994","unstructured":"Y.E. Nesterov and A.S. Nemirovsky,Interior Point Polynomial Algorithms in Convex Programming: Theory and Algorithms (SIAM Publications, Philadelphia, PA. 1994)."},{"key":"BF02614320_CR42","volume-title":"Mathematical Programming","author":"P.M. Pardalos","year":"1997","unstructured":"P.M. Pardalos and X. Lin, A tabu based pattern search method for the distance geometry problem, in: F. Giannessis et al., eds.,Mathematical Programming (Kluwer Academic Publishers, Dordrecht, 1997)."},{"key":"BF02614320_CR43","series-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1090\/dimacs\/020\/04","volume-title":"Combinatorial Optimization","author":"S. Poljak","year":"1995","unstructured":"S. Poljak and Z. Tuza, Maximum cuts and largest bipartite subgraphs, in: W. Cook, L. Lov\u00e1sz and P.D. Seymour, eds.,Combinatorial Optimization, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 20 (AMS, Providence, RI, 1995) 181\u2013244."},{"key":"BF02614320_CR44","first-page":"129","volume":"77","author":"M.V. Ramana","year":"1997","unstructured":"M.V. Ramana, An exact duality theory for semidefinite programming and its complexity implications,Mathematical Programming 77 (1997) 129\u2013162.","journal-title":"Mathematical Programming"},{"key":"BF02614320_CR45","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1080\/00029890.1981.11995175","volume":"88","author":"B. Roth","year":"1981","unstructured":"B. Roth, Rigid and flexible frameworks,The American Mathematical Monthly 88 (1981) 6\u201321.","journal-title":"The American Mathematical Monthly"},{"key":"BF02614320_CR46","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"D.J. Rose","year":"1976","unstructured":"D.J. Rose, R.E. Tarjan and G.S. Lueker, Algorithmic aspects of vertex elimination on graphs,SIAM Journal on Computing 5 (1976) 266\u2013283.","journal-title":"SIAM Journal on Computing"},{"key":"BF02614320_CR47","unstructured":"J.B. Saxe, Embeddability of weighted graphs ink-space is strongly NP-hard, in:Proc. 17th Allerton Conf. in Communications, Control and Computing (1979) 480\u2013489."},{"key":"BF02614320_CR48","doi-asserted-by":"crossref","first-page":"724","DOI":"10.2307\/1968654","volume":"36","author":"I.J. Schoenberg","year":"1935","unstructured":"I.J. Schoenberg, Remarks to M. Fr\u00e9chet\u2019s article \u201cSur la d\u00e9finition axiomatique d\u2019une classe d\u2019espaces vectoriels distanci\u00e9s applicables vectoriellement sur l\u2019espace de Hilbert\u201d,Annals of Mathematics 36 (1935) 724\u2013732.","journal-title":"Annals of Mathematics"},{"key":"BF02614320_CR49","doi-asserted-by":"crossref","first-page":"522","DOI":"10.1090\/S0002-9947-1938-1501980-0","volume":"44","author":"I.J. Schoenberg","year":"1938","unstructured":"I.J. Schoenberg, Metric spaces and positive definite functions,Transactions of the American Mathematical Society 44 (1938) 522\u2013536.","journal-title":"Transactions of the American Mathematical Society"},{"key":"BF02614320_CR50","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/0012-365X(85)90051-2","volume":"55","author":"R.E. Tarjan","year":"1985","unstructured":"R.E. Tarjan, Decomposition by clique separators,Discrete mathematics 55 (1985) 221\u2013232.","journal-title":"Discrete mathematics"},{"key":"BF02614320_CR51","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1002\/net.3230130202","volume":"13","author":"J.A. Wald","year":"1983","unstructured":"J.A. Wald and C.J. Colbourn, Steiner trees, partial 2-trees and minimum IFI networks,Networks 13 (1983) 159\u2013167.","journal-title":"Networks"},{"key":"BF02614320_CR52","series-title":"Encyclopedia of Mathematics and its Applications","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1017\/CBO9780511662041.002","volume-title":"Matroid Applications","author":"W. Whiteley","year":"1992","unstructured":"W. Whiteley, Matroids and rigid structures, in: N. White, ed.,Matroid Applications, Encyclopedia of Mathematics and its Applications, Vol. 40 (Cambridge University Press, Cambridge, MA, 1992) 1\u201353."},{"key":"BF02614320_CR53","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1126\/science.2911719","volume":"243","author":"K. W\u00fcthrich","year":"1989","unstructured":"K. W\u00fcthrich, Protein structure determination in solution by nuclear magnetic resonance spectroscopy,Science 243 (1989) 45\u201350.","journal-title":"Science"},{"key":"BF02614320_CR54","doi-asserted-by":"crossref","unstructured":"Y. Yemini, Some theoretical aspects of position-location problems, in:Proc. 20th Ann. Symp. on Foundations of Computer Science (1979) 1\u20138.","DOI":"10.1109\/SFCS.1979.39"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02614320.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02614320\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02614320","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T04:49:23Z","timestamp":1558327763000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02614320"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,10]]},"references-count":54,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[1997,10]]}},"alternative-id":["BF02614320"],"URL":"https:\/\/doi.org\/10.1007\/bf02614320","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,10]]}}}