Studies in algorithmic graph theory.
Item
-
Title
-
Studies in algorithmic graph theory.
-
Identifier
-
AAI9917628
-
identifier
-
9917628
-
Creator
-
Belianina, Maria.
-
Contributor
-
Adviser: Michael Anshel
-
Date
-
1999
-
Language
-
English
-
Publisher
-
City University of New York.
-
Subject
-
Mathematics | Computer Science
-
Abstract
-
Recently, L. H. Kauffman has introduced a planar cubic graph representation for the so called association equation. In addition, he has proven the equivalence between the Four Color Theorem (FCT) applied to a planar cubic graph and the existence of the solution for the corresponding association equation in a Vector Cross Product Algebra.;This thesis introduces an algorithm (AET) for transforming a planar cubic graph with described properties into a graph form corresponding to a single association equation. The theorems presented show the existence of such forms for planar cubic graphs whose dual graphs possess a Hamiltonian Cycle.;The method presented transforms a given Hamiltonian Cycle in the dual of the given graph into a closed curve in the original graph. This curve passes through each face of the original graph exactly once and does not touch any of its vertices. Next, it is demonstrated how to use the obtained closed curve to construct several "association equation - friendly" graph forms of the original graph. All of these forms are shown to correspond to a unique association equation which may take several equivalent forms of its own.;The thesis starts with discussion of an important algorithm (HCT) which transforms a given Hamiltonian Cycle into one or more Hamiltonian Cycles of the same graph. This algorithm generalizes the basic transformation technique of Papadimitriou's Hamiltonian Cycle transformation algorithm for cubic graphs. The paper presents a detailed proof of the algorithm's convergence. Applied to Kauffman's K - maps, each newly found Hamiltonian cycle (using the previously described AET method) produces another view of the same graph corresponding to a possibly new association equation. This algorithm is a non-deterministic one and can be randomized as shown.;Next, an auxiliary notion of an almost cubic graph is introduced and an algorithm (RA) is presented for reducing any graph to an almost cubic one. It is also shown that the HCT method applied to an almost cubic graph becomes more efficient and possibly even deterministic.;This work has also opened an interesting and challenging problem for future research: an algebraic analysis of the suggested HCT algorithm. It appears that using the operations on finite symmetry groups described in the thesis may be the direction to pursue.;Finally, new unconventional approaches to the Hamiltonian cycle problems are described in the section on DNA Computing, a new field on the edge of mathematics, computer science and molecular biology. The section presents a computer simulation of the biolab computing test on finding a Hamiltonian cycle in a graph.
-
Type
-
dissertation
-
Source
-
PQT Legacy CUNY.xlsx
-
degree
-
Ph.D.
