The real positive semidefinite completion problem for series-parallel graphs
From MaRDI portal
The author considers the partial real symmetric matrices \(X\) whose diagonal entries are equal to 1 and off-diagonal entries are specified only on a subset of the positions. The author gives a set of necessary conditions for \(X\) to be completable to a positive semidefinite matrix, and shows that these conditions are also sufficient if and only if the graph corresponding to the positions of the specified entries has no \(K_4\)-minor.
Recommendations
Cites work
- .878-approximation algorithms for MAX CUT and MAX 2SAT
- A Note on Extreme Correlation Matrices
- A note on extreme positive definite matrices
- All facets of the cut cone \(C_ n\) for \(n=7\) are known
- Connection between semidefinite relaxations of the max-cut and stable set problems
- Extremal correlation matrices
- 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
- Geometry. I, II. Transl. from the French by M. Cole and S. Levy
- scientific article; zbMATH DE number 4158856 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 780784 (Why is no real title available?)
- Matrix inequalities
- Nonpolyhedral Relaxations of Graph-Bisection Problems
- On a positive semidefinite relaxation of the cut polytope
- On cuts and matchings in planar graphs
- On the cut polytope
- On the Facial Structure of the Set of Correlation Matrices
- One-third-integrality in the max-cut problem
- Positive definite completions of partial Hermitian matrices
- Structural conditions for cycle completable graphs
- The real positive definite completion problem for a simple cycle
- The real positive definite completion problem: cycle completability
- Topology of series-parallel networks
Cited in
(24)- Positive semidefinite completions of partial Hermitian matrices
- Cuts, matrix completions and graph rigidity
- A connection between positive semidefinite and Euclidean distance matrix completion problems
- A parameterization of positive definite matrices in terms of partial correlation vines
- 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
- An efficient algorithm for maximum entropy extension of block-circulant covariance matrices
- Positive semidefinite matrix completion, universal rigidity and the strong Arnold property
- SPN completable graphs
- Complexity of the positive semidefinite matrix completion problem with a rank constraint
- Extremal positive semidefinite matrices whose sparsity pattern is given by graphs without \(K_{5}\) minors
- Computing the Grothendieck constant of some graph classes
- Critical Graphs for the Positive Definite Completion Problem
- Graph-Based Representations in Pattern Recognition
- Do sums of squares dream of free resolutions?
- Singularity degree of the positive semidefinite matrix completion problem
- On Sidorenko's conjecture for determinants and Gaussian Markov random fields
- Lectures on nonnegative polynomials and sums of squares
- Matrix completion and decomposition in phase-bounded cones
- Lissajous varieties
- 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
- Completion problem with partial correlation vines
- Positive semidefinite matrix completions on chordal graphs and constraint nondegeneracy in semidefinite programming
This page was built for publication: The real positive semidefinite completion problem for series-parallel graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q676039)
