Concepts of graph theory are frequently used by computer scientists as abstractions when modeling a problem. Partitioning a graph (or a network) into smaller parts is one of the fundamental algorithmic operations that plays a key role in classifying and clustering. Since the early 1970s, graph partitioning rapidly expanded for applications in wide areas. It applies in both engineering applications, as well as research. Current technology generates massive data (“Big Data”) from business interactions and social exchanges, so high-performance algorithms of partitioning graphs are a critical need.
This dissertation presents engineering models for two graph partitioning problems arising from completely different applications, computer networks and arithmetic. The design, analysis, implementation, optimization, and experimental evaluation of these models employ visualization in all aspects. Visualization indicates the performance of the implementation of each Algorithm Engineering work, and also helps to analyze and explore new algorithms to solve the problems. We term this research method as “Visualized Algorithm Engineering (VAE)” to emphasize the contribution of the visualizations in these works.
The techniques discussed here apply to a broad area of problems: computer networks, social networks, arithmetic, computer graphics and software engineering. Common terminologies accepted across these disciplines have been used in this dissertation to guarantee practitioners from all fields can understand the concepts we introduce.
David W. Matula
Number of Pages
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial 4.0 License
Chen, Zizhen, "Visualized Algorithm Engineering on Two Graph Partitioning Problems" (2023). Computer Science and Engineering Theses and Dissertations. 29.
LinkDetermination.mov (1648903 kB)
RGGDegeneracy.mov (1630514 kB)
SLColoring.mov (464813 kB)
RLColoring.mov (708641 kB)
RefineBackbone.mov (2238040 kB)
MatulaNumber.mov (173 kB)
PrimordialTree.mov (318 kB)
Constellation.mov (447986 kB)
PrimordialGarden.mov (124477 kB)
Graphics and Human Computer Interfaces Commons, Numerical Analysis and Scientific Computing Commons, Programming Languages and Compilers Commons, Software Engineering Commons, Theory and Algorithms Commons