2 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…