Visualized Algorithm Engineering on Two Graph Partitioning Problems

Authors

Zizhen Chen, Southern Methodist UniversityFollow

Abstract

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.

Degree Date

Spring 5-13-2023

Document Type

Dissertation

Degree Name

Ph.D.

Department

Computer Science and Engineering

Advisor

David W. Matula

Second Advisor

Ira Greenberg

Third Advisor

Eli Olinick

Fourth Advisor

Michael Hahsler

Fifth Advisor

Jennifer Dworak

Sixth Advisor

Frank Coyle

Subject Area

Computer Science

Number of Pages

109

Format

.pdf

Creative Commons License

This work is licensed under a Creative Commons Attribution-Noncommercial 4.0 License

Recommended Citation

Chen, Zizhen, "Visualized Algorithm Engineering on Two Graph Partitioning Problems" (2023). Computer Science and Engineering Theses and Dissertations. 29.
https://scholar.smu.edu/engineering_compsci_etds/29