Existing maximum flow algorithms use one processor for all calculations or one processor per vertex in a graph to calculate the maximum possible flow through a graph's vertices. This is not suitable for practical implementation. We extend the max-flow work of Goldberg and Tarjan to a distributed algorithm to calculate maximum flow where the number of processors is less than the number of vertices in a graph. Our algorithm is applied to maximizing electrical flow within a power network where the power grid is modeled as a graph. Error detection measures are included to detect problems in a simulated power network. We show that our algorithm is successful in executing quickly enough to prevent catastrophic power outages.

Meeting Name

29th Annual International Computer Software and Applications Conference (2005: Jul. 28, Edinburgh, UK)


Computer Science

Second Department

Electrical and Computer Engineering

Keywords and Phrases

FT Algorithms; FT Communication; FT Algorithms; FT Communication; Fault Injection; Distributed Algorithm; Distributed Algorithms; Distributed Max-Flow; Electrical Flow Maximization; Error Detection; Fault Injection; Graph Theory; Graph Vertex; Maximum Flow; Maximum Flow Algorithm; Optimisation; Power Grid Model; Power Network; Power Outage; Power System; Power Transmission Control

International Standard Serial Number (ISSN)


Document Type

Article - Conference proceedings

Document Version

Final Version

File Type





© 2005 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.

Publication Date

01 Jul 2005