A polynomial algorithm for deciding the validity of an electrical distribution tree

Dominique Barth (1) , Thierry Mautor (1) , Dimitri Watel (2, 3, 4) , Marc-Antoine Weisser (5, 6)

1 DAVID - Données et algorithmes pour une ville intelligente et durable - DAVID
2 IP Paris - Institut Polytechnique de Paris
3 METHODES-SAMOVAR - Méthodes et modèles pour les réseaux
4 ENSIIE - Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise
5 CentraleSupélec
6 LISN - Laboratoire Interdisciplinaire des Sciences du Numérique

We consider power distribution networks containing source nodes producing electricity and nodes representing electricity consumers interconnected by a switched network. Configuring this network consists in deciding which switches are activated and the orientation of the links between these switches, so as to obtain a directed graph from the producer nodes to the consumer nodes. This graph is valid if the electric flow it induces satisfies the demand of each consumer without exceeding the production capacity of each source and the flow capacity of each switch. We show that deciding if such a valid configuration exists is polynomial in a tree.

Mots clés: Complexity; Electrical network flow; Dynamic programming

Domaines: Complexité [cs.CC]; Algorithme et structure de données [cs.DS]

Dominique Barth, Thierry Mautor, Dimitri Watel, Marc-Antoine Weisser. A polynomial algorithm for deciding the validity of an electrical distribution tree. Information Processing Letters, 2022, 176, pp.106249. ⟨10.1016/j.ipl.2022.106249⟩. ⟨hal-04113551⟩