The real positive semidefinite completion problem for series-parallel graphs

DOI10.1016/0024-3795(95)00741-5zbMath0871.05043OpenAlexW2111230388MaRDI QIDQ676039

Monique Laurent

Publication date: 11 May 1997

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: https://ir.cwi.nl/pub/5067

zbMATH Keywords

real symmetric matricespositive semidefinite matrix

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items

Extremal positive semidefinite matrices whose sparsity pattern is given by graphs without \(K_{5}\) minors, Completion problem with partial correlation vines, Cuts, matrix completions and graph rigidity, A connection between positive semidefinite and Euclidean distance matrix completion problems, Do Sums of Squares Dream of Free Resolutions?, On Sidorenko's conjecture for determinants and Gaussian Markov random fields, Computing the Grothendieck constant of some graph classes, A parameterization of positive definite matrices in terms of partial correlation vines, An efficient algorithm for maximum entropy extension of block-circulant covariance matrices, Positive semidefinite matrix completion, universal rigidity and the strong Arnold property, A linear time algorithm for a variant of the MAX CUT problem in series parallel graphs, A new graph parameter related to bounded rank positive semidefinite matrix completions, Singularity Degree of the Positive Semidefinite Matrix Completion Problem, Positive semidefinite matrix completions on chordal graphs and constraint nondegeneracy in semidefinite programming, Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope, A maximum entropy approach to the realizability of spin correlation matrices, Complexity of the Positive Semidefinite Matrix Completion Problem with a Rank Constraint

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On cuts and matchings in planar graphs
• Positive definite completions of partial Hermitian matrices
• Extremal correlation matrices
• Structural conditions for cycle completable graphs
• Extreme points of a convex subset of the cone of positive semidefinite matrices
• Facets for the cut cone. I
• Facets for the cut cone. II: Clique-web inequalities
• A note on extreme positive definite matrices
• The real positive definite completion problem for a simple cycle
• Connection between semidefinite relaxations of the max-cut and stable set problems
• All facets of the cut cone \(C_ n\) for \(n=7\) are known
• On a positive semidefinite relaxation of the cut polytope
• One-third-integrality in the max-cut problem
• Topology of series-parallel networks
• .879-approximation algorithms for MAX CUT and MAX 2SAT
• A Note on Extreme Correlation Matrices
• On the cut polytope
• Nonpolyhedral Relaxations of Graph-Bisection Problems
• The real positive definite completion problem: cycle completability
• On the Facial Structure of the Set of Correlation Matrices
• Geometry. I, II. Transl. from the French by M. Cole and S. Levy
• Matrix inequalities