Current Search: HSUEH, CHI-FU (x)
-
-
Title
-
THE MINIMUM K-CENTER PROBLEM FOR GRID GRAPH.
-
Creator
-
HSUEH, CHI-FU, Florida Atlantic University, Hadlock, Frank O., Hoffman, Frederick, Charles E. Schmidt College of Science, Department of Mathematical Sciences
-
Abstract/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...
Show moreA 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.
Show less
-
Date Issued
-
1981
-
PURL
-
http://purl.flvc.org/fcla/dt/14077
-
Subject Headings
-
Graph theory, Algorithms
-
Format
-
Document (PDF)
