On Center Cycles in Grid 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 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 analyse rectangles in grid graphs with, in sequence, fixed dimension, fixed cardinality, and variable cardinality. In all cases a com plete 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 small cardinalities such that the center cycle problem in grid graphs is in these cases completely solved.

Volltext Dateien herunterladen

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar
Verfasserangaben:Horst W. Hamacher, Anita Schöbel
URN (Permalink):urn:nbn:de:hbz:386-kluedo-8095
Schriftenreihe (Bandnummer):Berichte des Fraunhofer-Instituts für Techno- und Wirtschaftsmathematik (ITWM Report) (11)
Sprache der Veröffentlichung:Englisch
Jahr der Fertigstellung:1998
Jahr der Veröffentlichung:1998
Veröffentlichende Institution:Fraunhofer-Institut für Techno- und Wirtschaftsmathematik
Datum der Publikation (Server):17.09.1999
Freies Schlagwort / Tag:Grid Graphs; center and median problems; locational analysis; variable cardinality case
The work of both authors was partially supported by a grant of the Deutsche Forschungsgemeinschaft
Fachbereiche / Organisatorische Einheiten:Fraunhofer (ITWM)
DDC-Sachgruppen:5 Naturwissenschaften und Mathematik / 510 Mathematik
Lizenz (Deutsch):Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011