From structure to performance: Algorithms and heuristics for graph bandwidth minimization.

摘要

Structure is a pattern that is present in problems, in problem-solving methods, and in solutions to problems. Performance quantifies the efficiency of resource utilization and the quality of solution, with respect to a problem-solving method, based on appropriate metrics. This research demonstrates how structure impacts the performance in the context of a specific graph problem called Graph Bandwidth Minimization (GBM).; Well known GBM heuristics exploit structures such as the level-structure, the degrees of nodes, the order in which nodes are selected for labeling, and the start node in which the labeling begins. The results reported demonstrate that these relationships are non-trivial. The impact on performance is different depending on whether the input graph is a graph of low bandwidth or a graph of high bandwidth. The results also demonstrate that a simple variation of BFS traversal identifies level-structures of lower width than the GPS heuristic for GBM.; BFS is shown to be a useful technique for identifying labelings of low bandwidth. Two variations of the basic BFS traversal that yield labelings of low bandwidth are presented. One of these variations can be parallelized efficiently.; Since BFS is a core component of sequential GBM heuristics, these heuristics cannot be efficiently parallelized. New implementations for GBM heuristics are presented based on high-level list operations. A new graph theoretic characterization demonstrates the relationship between ear decompositions and bandwidth 2 labelings for a biconnected graph. The characterization leads to a simple parallel algorithm. The characterization and the algorithm easily extends to the case of 2-edge connected, bandwidth 2 graphs as well as topological bandwidth 2 graphs.; Experimental results demonstrate that a genetic algorithm formulation for solving GBM fails to identify labelings of low bandwidth. A new evolutionary computation heuristic based on the behavior of a colony of ants is presented. The Ant System heuristic performs better than the genetic algorithm approach and is not as effective as the other GBM heuristics in all cases.