Cuts, matrix completions and graph rigidity

DOI10.1007/BF02614320zbMath0887.90174OpenAlexW2063936458MaRDI QIDQ1365058

Monique Laurent

Publication date: 25 May 1998

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02614320

zbMATH Keywords

semidefinite programmingmatrix completionEuclidean distance matricescutpolyhedral combinatoricsgraph rigiditygraph realization problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items

Phase retrieval of complex and vector-valued functions, Weak Rigidity Theory and Its Application to Formation Stabilization, Noisy Euclidean Distance Realization: Robust Facial Reduction and the Pareto Frontier, Cycle-based formulations in distance geometry, A parameterization of positive definite matrices in terms of partial correlation vines, Graph rigidity via Euclidean distance matrices, Iterated linear optimization, On rigidity and realizability of weighted graphs, Semidefinite programming for discrete optimization and matrix completion problems, A direct proof for the matrix decomposition of chordal-structured positive semidefinite matrices, The Euclidean distance degree of an algebraic variety

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The real positive semidefinite completion problem for series-parallel graphs
• On cuts and matchings in planar graphs
• On rigid circuit graphs
• Positive definite completions of partial Hermitian matrices
• Extremal correlation matrices
• Decomposition by clique separators
• Structural conditions for cycle completable graphs
• The ellipsoid method and its consequences in combinatorial optimization
• Forests, frames, and games: Algorithms for matroid sums and applications
• Geometric algorithms and combinatorial optimization
• The real positive definite completion problem for a simple cycle
• Problems of distance geometry and convex properties of quadratic maps
• An exact duality theory for semidefinite programming and its complexity implications
• An interior-point method for approximate positive semidefinite completions
• On a positive semidefinite relaxation of the cut polytope
• Topology of series-parallel networks
• On graphs and rigidity of plane skeletal structures
• Remarks to Maurice Frechet's article ``Sur la definition axiomatique d'une classe d'espaces vectoriels distancies applicables vectoriellement sur l'espace de Hilbert
• Über eine Punktverteilung auf der Kugel
• Steiner trees, partial 2–trees, and minimum IFI networks
• Asymptotic Properties of Discrete Unitary Transforms
• Rigid and Flexible Frameworks
• On Generic Rigidity in the Plane
• Conditions for Unique Graph Realizations
• Algorithmic Aspects of Vertex Elimination on Graphs
• A Note on Extreme Correlation Matrices
• On the cut polytope
• Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
• The Euclidian Distance Matrix Completion Problem
• The Euclidean distance completion problem: cycle completability
• The Molecule Problem: Exploiting Structure in Global Optimization
• The real positive definite completion problem: cycle completability
• Minimum partition of a matroid into independent subsets
• Geometry of cuts and metrics