Presentation
Solving Maximum Flows of Undirected Graphs by Minimizing s-t Effective Resistances of Electrical Networks
DescriptionWe introduce a practically efficient algorithm for approximating maximum flows in large undirected graphs based on the recent high-performance spectral algorithms. Our approach exploits a resistor-network optimization framework that can be further accelerated by leveraging nearly linear-time graph Laplacian solvers. By iteratively sizing up highly-congested edges and sizing down the edges with high effective s-t resistance sensitivities, approximate maximum flows can be obtained in a highly-efficient manner. The proposed method also has been extended for solving multi-commodity flow problems. We demonstrate the effectiveness and efficiency of the proposed approach by comparing it with the prior state-of-the-art methods on IBM VLSI benchmarks and other public-domain networks such as social networks.
Event Type
Work-in-Progress Poster
TimeWednesday, June 265:00pm - 6:00pm PDT
LocationLevel 2 Lobby
AI
Autonomous Systems
Cloud
Design
EDA
Embedded Systems
IP
Security