Note
Thesis (M.S.)--Florida Atlantic University, 1981.
Member of
Contributors
Publisher
Florida Atlantic University
Date Issued
1981
Description
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.
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.
Language
Type
Form
Extent
69 p.
Subject (Topical)
Identifier
14077
Additional Information
Thesis (M.S.)--Florida Atlantic University, 1981.
Charles E. Schmidt College of Science
FAU Electronic Theses and Dissertations Collection
Date Backup
1981
Date Text
1981
Date Issued (EDTF)
1981
Extension
FAU
FAU
admin_unit="FAU01", ingest_id="ing1508", creator="staff:fcllz", creation_date="2007-07-19 02:04:15", modified_by="staff:fcllz", modification_date="2011-01-06 13:09:06"
IID
FADT14077
Issuance
monographic
Organizations
Attributed name: Florida Atlantic University
Attributed name: Charles E. Schmidt College of Science
Attributed name: Department of Mathematical Sciences
Person Preferred Name
HSUEH, CHI-FU
Graduate College
Physical Description
69 p.
application/pdf
Title Plain
MINIMUM K-CENTER PROBLEM FOR GRID GRAPH
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.
http://rightsstatements.org/vocab/InC/1.0/
Origin Information
1981
monographic
Boca Raton, FL
Florida Atlantic University
Physical Location
Florida Atlantic University Libraries
Place
Boca Raton, FL
Sub Location
Digital Library
Title
MINIMUM K-CENTER PROBLEM FOR GRID GRAPH
Other Title Info
THE
MINIMUM K-CENTER PROBLEM FOR GRID GRAPH