Testability of minimum balanced multiway cut densities
From MaRDI portal
Abstract: Testable weighted graph parameters and equivalent notions of testability are investigated based on papers of Laszlo Lovasz and coauthors. We prove that certain balanced minimum multiway cut densities are testable. Using this fact, quadratic programming techniques are applied to approximate some of these quantities. The problem is related to cluster analysis and statistical physics. Convergence of special noisy graph sequences is also discussed.
Recommendations
- Lower threshold ground state energy and testability of minimal balanced cut density
- Density-constrained graph clustering
- Modularity spectra, eigen-subspaces, and structure of weighted graphs
- Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
- scientific article; zbMATH DE number 996908
Cites work
- scientific article; zbMATH DE number 3748742 (Why is no real title available?)
- scientific article; zbMATH DE number 1263204 (Why is no real title available?)
- Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
- Generalized quasirandom graphs
- Graph limits and parameter testing
- Limits of dense graph sequences
- Property testing and its connection to learning and approximation
- Quick approximation to matrices and applications
- Recognizing linear structure in noisy matrices
Cited in
(3)
This page was built for publication: Testability of minimum balanced multiway cut densities
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q423907)
