Subject Area

Computer Science

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

Number of Pages

109

Format

.pdf

Creative Commons License

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

SensorDeployment.mov (507780 kB)
Sensor Deployment

LinkDetermination.mov (1648903 kB)
Link Determination

RGGDegeneracy.mov (1630514 kB)
RGG Degeneracy

SLColoring.mov (464813 kB)
Smallest-last Coloring

RLColoring.mov (708641 kB)
Relay Coloring

RefineBackbone.mov (2238040 kB)
Backbone Refinement

MatulaNumber.mov (173 kB)
Matula Number

PrimordialTree.mov (318 kB)
Primordial Tree

Constellation.mov (447986 kB)
Primordial Constellation

PrimordialGarden.mov (124477 kB)
Primordial Garden

Share

COinS