[pt] META-HEURÍSTICAS PARA O PROBLEMA DE INCORPORAÇÃO LINEAR PARA O NÚMERO DE CRUZAMENTOS

[en] METAHEURISTICS FOR THE LINEAR EMBEDDING CROSSING MINIMIZATION PROBLEM

[pt] HANDEL SCHOLZE MARQUES

[pt] GRAFO

[pt] NP-COMPLETO

[pt] GRAFO PLANAR

[pt] RECOZIMENTO SIMULADO

[pt] META-HEURISTICA

[en] GRAPH

[en] NP-COMPLETE

[en] PLANAR GRAPH

[en] SIMULATED ANNEALING

[en] META-HEURISTICS

[pt] A teoria dos grafos desempenha um papel fundamental tanto na matemática teórica quanto aplicada, na ciência da computação e na engenharia decomputação, influenciando significativamente o design e a análise de sistemascomplexos em domínios como arquiteturas de software, redes sociais e componentes elétricos. Um desafio crucial dentro deste campo é a minimização decruzamentos de arestas em desenhos de grafos, o que aumenta a clareza visuale reduz possíveis erros em circuitos eletrônicos e diagramas de fluxo de dados. Este trabalho investiga especificamente a minimização de cruzamentos dearestas em incorporações lineares de grafos, onde os vértices são alinhados aolongo de uma reta, referido como espinha, e as arestas são distribuídas emmúltiplos semi-planos, conhecidos como páginas, que se intersectam nestaespinha.Devido à natureza NP-Completa do problema, buscar soluções exatas éfrequentemente impraticável. Consequentemente, este estudo concentra-se naaplicação de meta-heurísticas, especificamente Recozimento Simulado e Pesquisa Local Iterada, como métodos robustos para enfrentar essa complexidade.Essas técnicas são exploradas em profundidade para demonstrar sua eficáciana navegação eficaz do espaço de busca, fornecendo assim soluções viáveis queaproximam o número mínimo de cruzamentos para várias configurações degrafos.Os resultados desta pesquisa destacam a adaptabilidade e o potencial dasabordagens meta-heurísticas no gerenciamento de desafios em teoria dos grafos. Por meio de análise comparativa e validação experimental, este trabalhoestabelece um modelo para estudos futuros para refinar e expandir as estraté-gias discutidas, oferecendo potencialmente novas vias para abordar problemasde otimização combinatória na teoria dos grafos e além.

[en] Graph theory plays a pivotal role in theoretical and applied mathematics, computing science, and computer engineering, significantly influencing the design and analysis of complex systems across domains such as software architectures, social networks, and electrical components. A crucial challenge within this field is the minimization of edge crossings in graph drawings, which enhances visual clarity and reduces potential errors in electronic circuits and data flow diagrams. This work specifically investigates the minimization of edge crossings in linear embeddings of graphs, where vertices are aligned along a singular linear axis, referred to as the spine, and edges are distributed across multiple semi-planes, known as pages, that intersect at this spine. Due to the NP-Complete nature of the problem, seeking exact solutions is often impractical. Consequently, this study focuses on the application of metaheuristics, specifically Simulated Annealing and Iterated Local Search, as robust methods to address this complexity. These techniques are explored in depth to demonstrate their efficacy in navigating the search space effectively, thereby providing feasible solutions that approximate the minimal crossing numbers for various graph configurations. The findings of this research highlight the adaptability and potential of metaheuristic approaches in managing challenges in graph theory. Through comparative analysis and experimental validation, this work establishes a framework for future studies to refine and expand upon the strategies discussed, potentially offering new avenues for addressing combinatorial optimization problems in graph theory and beyond.

AUGUSTO CESAR ESPINDOLA BAFFA

RAFAEL MARTINELLI PINTO

2024-09-06

[pt] TEXTO

application/pdf

INGLÊS

https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=67884@1

https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=67884@2

https://doi.org/10.17771/PUCRio.acad.67884