An augmenting‐flow algorithm for a class of node‐capacitated maximum flow problems. Issue 1 (16th November 2021)

• Record Type: Journal Article
• Authors: Curry, Robert M.; Smith, J. Cole
• Is Part Of: Networks. Volume 80:Issue 1(2022)
• Page Start: 109
• Page End: 122
• Publication Date: 2021-11-16
• Subjects: linear programming -- maximum flow problem -- network optimization -- node capacities; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.22082
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract: We consider a class of maximum flow problems (MFPs) having node‐ and arc‐capacity constraints, in which each unit of flow on arc ( i, j ) consumes a positive amount of capacity at node i . This problem arises in wireless sensor network optimization applications, where node capacities refer to sensor energy limits. This version of the MFP is traditionally solved using linear programming due to the presence of the complicating node‐capacity constraints. As an alternative scheme, we prescribe an approach for this problem based on augmenting flows along paths and cycles, showing why sending flows on augmenting cycles becomes necessary in this class of problems. Although our augmenting flow algorithm ultimately requires the solution of auxiliary linear programs, we demonstrate the computational advantages of our approach on randomly generated test instances.