Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


miami1237496109.pdf (883.42 KB)

ETD Abstract Container

Abstract Header

A NEW IMPLEMENTATION OF CLUSTERING ALGORITHM AND ITS APPLICATION IN NET-TREE CONSTRUCTION ALGORITHM

Dai, Yan
http://rave.ohiolink.edu/etdc/view?acc_num=miami1237496109

Abstract Details

2009, Master of Computer Science, Miami University, Computer Science and Systems Analysis.
In a vertex k-center problem, the goal is to pick some vertexes, called centers, from a given undirected weighted graph so as to minimize the maximum distance of any vertex from its closest center. It is known that not only is k-center an NP-complete problem, but approximating the k-center problem within a factor better than 2 is still NP-complete [2]. If the distance between any two vertices is given as a distance matrix (so distance computations take constant time), the 2-approximation k-center problem can be solved in O(n•logk) time [2]. But to build such a distance matrix for a large-size road map is impractical because even storing the distance matrix is impractical, because it requires n2 space. In this paper, I propose a new algorithm that gives a 2-approximation to the vertex k-center problem in O(λ2•n•logn•logφ) time in road maps, where λ is the doubling constant and φ is the spread of the graph, without being given the distance matrix in advance.
Bo Brinkman, PhD (Advisor)
Alton Sanders, PhD (Committee Member)
Keith Frikken, PhD (Committee Member)
33 p.
Computer Science
clustering; k-center; net-tree; geometric algorithm; doubling dimension; doubling constant

Recommended Citations

Citations

  • Dai, Y. (2009). A NEW IMPLEMENTATION OF CLUSTERING ALGORITHM AND ITS APPLICATION IN NET-TREE CONSTRUCTION ALGORITHM [Master's thesis, Miami University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=miami1237496109

    APA Style (7th edition)

  • Dai, Yan. A NEW IMPLEMENTATION OF CLUSTERING ALGORITHM AND ITS APPLICATION IN NET-TREE CONSTRUCTION ALGORITHM. 2009. Miami University, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=miami1237496109.

    MLA Style (8th edition)

  • Dai, Yan. "A NEW IMPLEMENTATION OF CLUSTERING ALGORITHM AND ITS APPLICATION IN NET-TREE CONSTRUCTION ALGORITHM." Master's thesis, Miami University, 2009. http://rave.ohiolink.edu/etdc/view?acc_num=miami1237496109

    Chicago Manual of Style (17th edition)

miami1237496109
538
© 2009, all rights reserved.
This open access ETD is published by Miami University and OhioLINK.