Dissertation/Thesis Abstract

Reconstructing Approximate Tree Metrics and Using Them to Approximate Min-Max Clustering Problem
by Ladoia, Mayank, M.S., Kent State University, 2012, 65; 10631127
Abstract (Summary)

In this thesis we consider the problem of embedding a graph metric into a tree metric so that the distances in graph are closely resembled by the distances in the tree . We modify a known best algorithm for the problem and analyze its performance on large real-life networks. Our experimentation shows that many real-life networks are embeddable into trees with very small distortions. These low distortion embeddings can be used to obtain good approximate solutions to many problems related to distances in graph. We demonstrate this on the well-known min-max clustering problem.

Indexing (document details)
Commitee: Dragan, Feodor F., Jin, Ruoming, Maletic, Jonathan I.
School: Kent State University
Department: College of Arts and Sciences / Department of Computer Science
School Location: United States -- Ohio
Source: MAI 56/05M(E), Masters Abstracts International
Subjects: Computer science
Publication Number: 10631127
ISBN: 978-0-355-01420-4
Copyright © 2020 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy