Testability of minimum balanced multiway cut densities

DOI10.1016/J.DAM.2011.12.005zbMATH Open1239.05084arXiv1001.1623OpenAlexW2161720717MaRDI QIDQ423907FDOQ423907

András Krámli, Tamás Kói, Marianna Bolla

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

zbMATH Keywords

fuzzy clusteringminimum balanced multiway cutstestable weighted graph parametersWigner-noise

Mathematics Subject Classification ID

Signed and weighted graphs (05C22)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Limits of dense graph sequences
• Generalized quasirandom graphs
• Property testing and its connection to learning and approximation
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Recognizing linear structure in noisy matrices
• Quick approximation to matrices and applications
• Graph limits and parameter testing

Cited In (3)

• Generalized quasirandom properties of expanding graph sequences
• Lower threshold ground state energy and testability of minimal balanced cut density
• Modularity spectra, eigen-subspaces, and structure of weighted graphs

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)