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

作　　者：CHANG KungChing SHAO SiHong ZHANG Dong 

机构地区：[1]LMAM and School of Mathematical Sciences, Peking University

出　　处：《Science China Mathematics》2017年第11期1963-1980,共18页中国科学：数学（英文版）

基　　金：supported by National Natural Science Foundation of China (Grant Nos. 11371038, 11471025, 11421101 and 61121002)

摘　　要：This is primarily an expository paper surveying up-to-date known results on the spectral theory of1-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.This is primarily an expository paper surveying up-to-date known results on the spectral theory of1-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.

关 键 词：spectral graph theory Laplacian graph cut optimization critical point theory 

分 类 号：O157.5[理学—数学]