An efficient program for cycle basis selection and bandwidth optimization. (English) Zbl 1207.05118
Summary: The applicability of graph theory for optimizing the sparsity and the bandwidth of cycle adjacency matrices of graphs is shown. Fundamental and subminimal cycle basis selection algorithms are presented in an algorithmic way.
It is shown how the pattern of the cycle adjacency matrix changes during different phases of cycle selection and in particular when cycles are ordered. At each stage small pieces of code are presented to illustrate the simplicity of the implementation of the graph theoretical approaches using a computer language such as C++. The use of other languages should not cause much difficulty, although many aspects of an object oriented language such as C++ have been employed extensively throughout. This is intended to demonstrate the efficiency of graph theoretical methods combined with advanced techniques of computer programming.
It is shown how the pattern of the cycle adjacency matrix changes during different phases of cycle selection and in particular when cycles are ordered. At each stage small pieces of code are presented to illustrate the simplicity of the implementation of the graph theoretical approaches using a computer language such as C++. The use of other languages should not cause much difficulty, although many aspects of an object oriented language such as C++ have been employed extensively throughout. This is intended to demonstrate the efficiency of graph theoretical methods combined with advanced techniques of computer programming.
MSC:
05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
05C85 | Graph algorithms (graph-theoretic aspects) |
68R10 | Graph theory (including graph drawing) in computer science |