التفاصيل البيبلوغرافية
| العنوان: |
On Center Cycles in Grid Graphs. |
| المؤلفون: |
Foulds, Les R.1 lfoulds@mngt.waikato.ac.nz, Hamacher, Horst W.2 hamacher@mathematik.uni-kl.de, Schöbel, Anita2 schoebel@mathematik.uni-kl.de, Yamaguchi, Tadashi3 tad.yama@do-johodai.ac.jp |
| المصدر: |
Annals of Operations Research. Sep2003, Vol. 122 Issue 1-4, p163-175. 13p. 7 Graphs. |
| مصطلحات موضوعية: |
*ALGORITHMS, *STANDARD deviations, *ECONOMICS, GRAPH theory, MEDIAN (Mathematics) |
| مستخلص: |
Finding “good” cycles in graphs is a problem of great interest in graph theory as well as in locational analysis. We show that the center and median problems are NP-hard in general graphs. This result holds both for the variable cardinality case (i.e., all cycles of the graph are considered) and the fixed cardinality case (i.e., only cycles with a given cardinality p are feasible). Hence it is of interest to investigate special cases where the problem is solvable in polynomial time. In grid graphs, the variable cardinality case is, for instance, trivially solvable if the shape of the cycle can be chosen freely. If the shape is fixed to be a rectangle one can analyze rectangles in grid graphs with, in sequence, fixed dimension, fixed cardinality, and variable cardinality. In all cases a complete characterization of the optimal cycles and closed form expressions of the optimal objective values are given, yielding polynomial time algorithms for all cases of center rectangle problems. Finally, it is shown that center cycles can be chosen as rectangles for bounded cardinalities such that the center cycle problem in grid graphs is in these cases completely solved. [ABSTRACT FROM AUTHOR] |
|
Copyright of Annals of Operations Research is the property of Springer Nature and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| قاعدة البيانات: |
Business Source Index |
Full Text Finder