You are here
MINIMUM K-CENTER PROBLEM FOR GRID GRAPH
| Title: | THE MINIMUM K-CENTER PROBLEM FOR GRID GRAPH. |
 93 views 17 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. |
