Testability of minimum balanced multiway cut densities
From MaRDI portal
Publication:423907
DOI10.1016/J.DAM.2011.12.005zbMATH Open1239.05084arXiv1001.1623OpenAlexW2161720717MaRDI QIDQ423907FDOQ423907
Authors: Marianna Bolla, Tamás Kói, András Krámli 
Publication date: 30 May 2012
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1001.1623
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
- Limits of dense graph sequences
- Generalized quasirandom graphs
- Property testing and its connection to learning and approximation
- Title not available (Why is that?)
- Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
- Recognizing linear structure in noisy matrices
- Title not available (Why is that?)
- Quick approximation to matrices and applications
- Graph limits and parameter testing
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)
