Cheeger's cut, maxcut and the spectral theory of 1-Laplacian on graphs

• 来源期刊: 中国科学：数学（英文版）
• 年，卷（期）: 2017,（11）
• 页码范围: 1963-1980
• 页数: 18页
• 语种: 英文
• DOI: 10.1007/s11425-017-9096-6

摘要

This is primarily an expository paper surveying up-to-date known results on the spectral theory of 1-Laplacian on graphs and its applications to the Cheeger cut,maxcut and multi-cut problems.The structure of eigenspace,nodal domains,multiplicities of eigenvalues,and algorithms for graph cuts are collected.