You are here

MINIMUM K-CENTER PROBLEM FOR GRID GRAPH

Download pdf | Full Screen View

Date Issued:
1981
Summary:
A study was made of the problem of locating M facilities on a connected grid graph, so that M is the minimum and so that every demand node on the graph is within given distance K of one of these M facilities. We call this problem briefly the G(N,K,M) problem, with N denoting the total number of demand nodes. An algorithm for solving this problem by using backtrack technique is presented in this thesis. A heuristic algorithm is also present; although the resulting M is not always minimum, it tends to be near minimum. The advantage over the backtrack algorithm is that the heuristic algorithm operates very quickly. Algorithms represented in this thesis are programmed in the Pascal language for the Univac 1100 computer at Florida Atlantic University, Boca Raton, Florida.
Title: THE MINIMUM K-CENTER PROBLEM FOR GRID GRAPH.
0 views
0 downloads
Name(s): HSUEH, CHI-FU
Florida Atlantic University, Degree grantor
Hadlock, Frank O., Thesis advisor
Hoffman, Frederick, Thesis advisor
Charles E. Schmidt College of Science
Department of Mathematical Sciences
Type of Resource: text
Genre: Electronic Thesis Or Dissertation
Issuance: monographic
Date Issued: 1981
Publisher: Florida Atlantic University
Place of Publication: Boca Raton, FL
Physical Form: application/pdf
Extent: 69 p.
Language(s): English
Summary: A study was made of the problem of locating M facilities on a connected grid graph, so that M is the minimum and so that every demand node on the graph is within given distance K of one of these M facilities. We call this problem briefly the G(N,K,M) problem, with N denoting the total number of demand nodes. An algorithm for solving this problem by using backtrack technique is presented in this thesis. A heuristic algorithm is also present; although the resulting M is not always minimum, it tends to be near minimum. The advantage over the backtrack algorithm is that the heuristic algorithm operates very quickly. Algorithms represented in this thesis are programmed in the Pascal language for the Univac 1100 computer at Florida Atlantic University, Boca Raton, Florida.
Identifier: 14077 (digitool), FADT14077 (IID), fau:10892 (fedora)
Degree granted: Thesis (M.S.)--Florida Atlantic University, 1981.
Collection: FAU Electronic Theses and Dissertations Collection
Note(s): Charles E. Schmidt College of Science
Subject(s): Graph theory
Algorithms
Held by: Florida Atlantic University Libraries
Persistent Link to This Record: http://purl.flvc.org/fcla/dt/14077
Sublocation: Digital Library
Use and Reproduction: Copyright © is held by the author with permission granted to Florida Atlantic University to digitize, archive and distribute this item for non-profit research and educational purposes. Any reuse of this item in excess of fair use or other copyright exemptions requires permission of the copyright holder.
Use and Reproduction: http://rightsstatements.org/vocab/InC/1.0/
Host Institution: FAU
Is Part of Series: Florida Atlantic University Digital Library Collections.