Reduction of Potential-Based Flow Networks

• 成果类型: Article
• 署名作者: Klimm, Max; Pfetsch, Marc E.; Raber, Rico; Skutella, Martin
• 署名单位: Technical University of Berlin; Technical University of Darmstadt
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2022.1338
• 发表日期: 2023
• 页码: 2287-2303
• 关键词: generalization error; smart predict; optimize

摘要

We consider potential-based flow networks with terminal nodes at which flow can enter or leave the network and physical properties, such as voltages or pressures, are measured and controlled. We study conditions under which such a network can be reduced to a smaller, equivalent network with the same behavior at the terminal nodes. Potential-based flow networks are widely used to model infrastructure networks, such as electricity, gas, or water networks. In contrast to Kron's reduction for electrical networks, we prove that, in general, potential-based flow networks with at least three terminals cannot be reduced to smaller networks whose size only depends on the number of terminals. On the other hand, we show that it is possible to represent a special class of potential-based flow networks by a complete graph on the terminals, and we establish a characterization of networks that can be reduced to a path network. Our results build on fundamental properties of effective resistances proved in this paper, including explicit formulae for their dependence on edge resistances of the network and their metric properties.