Modelling and solving central cycle problems with integer programming

Modelling and solving central cycle problems with integer programming

0.00 Avg rating0 Votes
Article ID: iaor20043460
Country: United Kingdom
Volume: 31
Issue: 7
Start Page Number: 1083
End Page Number: 1095
Publication Date: Jun 2004
Journal: Computers and Operations Research
Authors: , ,
Keywords: graphs, programming: integer
Abstract:

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. The problems have applications in facilities location, particularly the location of emergency facilities, and service facilities.

Reviews

Required fields are marked *. Your email address will not be published.