Singular value decomposition for information retrieval, graph bisection, and genetic algorithms
Martin, Jacob Gilmore
MetadataShow full item record
Singular value decomposition's usefulness in graph bisection,genetic algorithms, and information retrieval is studied. An infor-mation retrieval theorem about latent semantic indexing (LSI) ispresented in detail. Several theorems are proved concerning bi-section size guarantees when performing spectral bisection withthe singular value decomposition of adjacency matrices of certaingraphs. In addition, singular value decomposition is used in manyways to enhance a genetic algorithm's performance.Highlights of the results include:Clarification of a well known LSI theorem, with counterexam-ples.Improvement of heuristics for finding the minimum bisectionof a graph.Minimum bisection guarantees for graphs with a certain struc-tures using a new proof strategy.Empirical evidence that multiple eigenvectors can be useful inspectral bisection.Several novel applications of singular value decomposition ingenetic algorithms.
Showing items related by title, author, creator and subject.
Pootheri, Sridar Kuttan (uga, 2000-05)Applying the Tutte decomposition of 2-connected graphs into 3-block trees we provide unique structural characterizations of several classes of 2-connected graphs, including minimally 2-connected graphs, minimally ...
Pootheri, Sridar Kuttan (uga, 2000-05)Applying the Tutte decomposition of 2-connected graphys into 3-block trees, unique structural characterizations of several classes of 2-connected graphs were provided in the PhD dissertation of the author under the title ...
Xue, Mei (uga, 2001-05)This thesis explores randomized algorithms for _nding Hamilton cycles in cubic graphs.|After giving some basic de_nitions, we discuss an algorithm for generating random 3-regular graphs. This is used for testing. Then two ...