Loughborough University
Browse

Modelling and solving central cycle problems with integer programming

Download (466.53 kB)
preprint
posted 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.

History

School

  • Business and Economics

Department

  • Business

Pages

495700 bytes

Citation

FOULDS, 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

Publication date

2000

Notes

THIS 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.

ISBN

1859011675

Language

  • en