3 papers
cs.DS2023
Fast Algorithms for Directed Graph Partitioning Using Flows and Reweighted Eigenvalues
Lap Chi Lau, Kam Chuen Tung, Robert Wang
We consider a new semidefinite programming relaxation for directed edge expansion, which is obtained by adding triangle inequalities to the reweighted eigenvalue formulation. Apply…
cs.DS2022
Cheeger Inequalities for Directed Graphs and Hypergraphs Using Reweighted Eigenvalues
Lap Chi Lau, Kam Chuen Tung, Robert Wang
We derive Cheeger inequalities for directed graphs and hypergraphs using the reweighted eigenvalue approach that was recently developed for vertex expansion in undirected graphs [O…
cs.DS2022
Cheeger Inequalities for Vertex Expansion and Reweighted Eigenvalues
Tsz Chiu Kwok, Lap Chi Lau, Kam Chuen Tung
The classical Cheeger's inequality relates the edge conductance of a graph and the second smallest eigenvalue of the Laplacian matrix. Recently, Olesker-Taylor and Zanett…