2000-6.pdf (466.53 kB)
Modelling and solving central cycle problems with integer programming
preprintposted on 2006-05-26, 12:42 authored by L.R. Foulds, John Wilson, T. Yamaguchi
We consider the problem of identifying a central subgraph of a given simple connected graph. The case where the subgraph comprises a discrete set of vertices is well known. However, the concept of eccentricity can be extended to connected subgraphs such as: paths, trees and cycles. Methods have been reported which deal with the requirement that the subgraph is a path or a constrained tree. We extend this work to the case where the subgraph is required to be a cycle. We report on computational experience with integer programming models of the problems of identifying cycle centres, cycle medians and cycle centroids, and also on a heuristic based on the first model. The problems have applications in facilities location, particularly the location of emergency facilities, and service facilities.
- Business and Economics
CitationFOULDS, L.R., WILSON, J.M. and YAMAGUCHI, T., 2000. Modelling and solving central cycle problems with integer programming. Occasional Paper 2000:6, Loughborough: Business School, Loughborough University.
Publisher© Loughborough University
NotesTHIS PAPER IS CIRCULATED FOR DISCUSSION PURPOSES AND ITS CONTENTS SHOULD BE CONSIDERED PRELIMINARY AND CONFIDENTIAL. NO REFERENCE TO MATERIAL CONTAINED HEREIN MAY BE MADE WITHOUT THE CONSENT OF THE AUTHORS.