TY - JOUR AU - Juan Carlos García Ojeda PY - 2020/09/09 Y2 - 2024/03/29 TI - A Look at Algorithm BEPtoPNST JF - Revista Ingenierías Universidad de Medellín JA - rev.ing.univ.Medellin VL - 20 IS - 39 SE - Articles DO - 10.22395/rium.v20n39a7 UR - https://revistas.udem.edu.co/index.php/ingenierias/article/view/3084 AB - This work analyzes the computational complexity of algorithm BEPtoPNST which transforms a building-evacuation problem (BEP) into a time-ex-panded, process-network synthesis (PNST) problem. The solution of the latter is achieved by resorting to the P-graph method which exploits the combinatorial nature of a BEP. Unlike other approaches, the P-graph method provides not only the optimal solution (best evacuation route as a function of egress time), but also the best n sub-optimal solutions. For the complexity analysis, a generic processor, and a Random-access machine (RAM) model were deployed as well as a mathematical model to calculate the number and cost of the operations performed. It was observed that algorithm BEPtoPNST exhibits an asymptotic complexity of order O ( T | A | (| N | –k)). When solving a BEP, however, the total complexity grows exponentially with order O (T | A | (| N | –k)) + O (2h)) in the worst case; where h represents the total number of operating units specified in the corresponding PNST problem. Nevertheless, the computational comple-xity can be reduced significantly when the P-graph method is deployed. ER -