Base de ciclos mínima no fluxo de potência ótimo
DOI:
https://doi.org/10.5540/03.2023.010.01.0027Keywords:
Base de Ciclos Mínima, Matriz Ciclo, Esparsidade, Fluxo de Potência ÓtimoAbstract
Uma base de ciclos mínima fornece uma estrutura esparsa para a matriz ciclo de um grafo, que é utilizada como uma etapa de pré-processamento em várias aplicações. Neste trabalho, analisamos métodos para encontrar uma base de ciclos mínima, implementamos e realizamos testes computacionais utilizando os sistemas de teste do Institute of Electrical and Electronics Engineers (IEEE) e sistemas brasileiros de grande porte. Os resultados apontam que a matriz ciclo gerada por uma base aproximada de ciclos mínima é uma alternativa interessante para aplicações em redes elétricas, pois apresenta um equilíbrio viável entre o tempo de processamento e a esparsidade da matriz.
Downloads
References
E. W. Dijkstra. “A note on two problems in connexion with graphs”. Em: Edsger Wybe Dijkstra: His Life, Work, and Legacy. Ed. por Hoare T. Krzysztof R. A. Vol. 45. Association for Computing Machinery, 2022. Cap. 14, pp. 287–290.
R. W. Floyd. “Algorithm 97: Shortest Path”. Em: Commun. ACM 6 (1962), pp. 345–350. doi: 10.1145/367766.368168.
P. M. Gleiss. “Short Cycles Minimum Cycle Bases of Graphs from Chemistry and Biochemistry”. Tese de doutorado. Faculty of Science e Mathematics from the University of Wien, 2001.
A. Golynski e J. D. Horton. “A polynomial time algorithm to find the minimum cycle basis of a regular matroid”. Em: Scandinavian Workshop on Algorithm Theory. 2002, pp. 200–209. doi: 10.1007/3-540-45471-3_21.
D. Hartvigsen e R. Mardon. “The all-pairs min cut problem and the minimum cycle basis problem on planar graphs”. Em: SIAM Journal on Discrete Mathematics 3 (1994), pp. 403–418. doi: 10.1137/S0895480190177042.
J. D. Horton. “A polynomial-time algorithm to find the shortest cycle basis of a graph”. Em: SIAM Journal on Computing 2 (1987), pp. 358–366. doi: 10.1137/0216026.
T. Kavitha et al. “A faster algorithm for minimum cycle basis of graphs”. Em: Automata, Languages and Programming: 31st International Colloquium, ICALP 2004, Turku, Finland, July 12-16, 2004. Proceedings 31. 2004, pp. 846–857. doi: 10.1007/978-3-540-27836-8_71.
T. Kavitha et al. “Cycle bases in graphs characterization, algorithms, complexity, and applications”. Em: Computer Science Review 4 (2009), pp. 199–243. doi: 10.1016/j.cosrev.2009.08.001.
A. R. L. Oliveira, S. Soares e L. Nepomuceno. “Optimal active power dispatch combining network flow and interior point approaches”. Em: IEEE Transactions on Power Systems 4 (2003), pp. 1235–1240. doi: 10.1109/TPWRS.2003.814851.
J. C. Pina. “Applications of shortest path methods”. Tese de doutorado. University of Amsterdam, 1995.
