Cheeger's cut, maxcut and the spectral theory of 1-Laplacian on graphs
From MaRDI portal
Publication:724411
DOI10.1007/s11425-017-9096-6zbMath1391.05159OpenAlexW2743235928MaRDI QIDQ724411
Dong Zhang, Sihong Shao, Kung-Ching Chang
Publication date: 25 July 2018
Published in: Science China. Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s11425-017-9096-6
Extremal problems in graph theory (05C35) Combinatorial optimization (90C27) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Spectral theory; eigenvalue problems on manifolds (58C40)
Related Items (10)
Nonsmooth critical point theory and applications to the spectral graph theory ⋮ Gradient flows in metric random walk spaces ⋮ The Cheeger cut and Cheeger problem in metric graphs ⋮ An entropy-regularized ADMM for binary quadratic programming ⋮ The Cheeger cut and Cheeger problem in metric measure spaces ⋮ The total variation flow in metric random walk spaces ⋮ The limit of first eigenfunctions of the \(p\)-Laplacian on graphs ⋮ Dirichlet \(p\)-Laplacian eigenvalues and Cheeger constants on symmetric graphs ⋮ Delta invariant for Eulerian digraphs ⋮ Data clustering based on the modified relaxation Cheeger cut model
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A feasible method for optimization with orthogonality constraints
- Nodal domains of eigenvectors for 1-Laplacian on graphs
- An unconstrained minimization method for solving low-rank SDP relaxations of the maxcut problem
- A framework of constraint preserving update schemes for optimization on Stiefel manifold
- Variational methods for non-differentiable functionals and their applications to partial differential equations
- Laplacian eigenvalues and the maximum cut problem
- Solving the max-cut problem using eigenvalues
- Laplacians on infinite graphs: Dirichlet and Neumann boundary conditions
- Bipartite and neighborhood graphs and the spectrum of the normalized graph Laplace operator
- Laplacian eigenvectors of graphs. Perron-Frobenius and Faber-Krahn type theorems
- Rank-Two Relaxation Heuristics for MAX-CUT and Other Binary Quadratic Programs
- Advanced Scatter Search for the Max-Cut Problem
- The 1-Laplacian Cheeger Cut: Theory and Algorithms
- Spectrum of the 1-Laplacian and Cheeger's Constant on Graphs
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Max Cut and the Smallest Eigenvalue
- Reducibility among Combinatorial Problems
- Multi-way spectral partitioning and higher-order cheeger inequalities
- An algorithm for finding shortest routes from all source nodes to a given destination in general networks
This page was built for publication: Cheeger's cut, maxcut and the spectral theory of 1-Laplacian on graphs
