Article ID: | iaor20042484 |
Country: | Netherlands |
Volume: | 122 |
Issue: | 1 |
Start Page Number: | 163 |
End Page Number: | 175 |
Publication Date: | Sep 2003 |
Journal: | Annals of Operations Research |
Authors: | Hamacher Horst W., Schbel Anita, Foulds Les R., Yamaguchi Tadashi |
Keywords: | graphs |
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