Optimum requirement Hamilton cycle problem with a Monge-like property

Optimum requirement Hamilton cycle problem with a Monge-like property

0.00 Avg rating0 Votes
Article ID: iaor20023406
Country: Japan
Volume: 45
Issue: 1
Start Page Number: 36
End Page Number: 43
Publication Date: Mar 2002
Journal: Journal of the Operations Research Society of Japan
Authors:
Keywords: networks, programming: network
Abstract:

Given a simple graph G with a vertex set V and a set of ‘requirements’ {rvw | v, w ∈ V}, we consider a problem to find a Hamilton cycle minimizing an objective function similar to that in the optimum requirement spanning tree problem studied by Hu. And we show that a particular Hamilton cycle C* which is explicitly definable is a solution to the problem when G is complete and {rvw} satisfies inverse Supnick property closely related to Monge property. It is of great interest that C* is also a solution to the symmetric traveling salesman problem with (not inverse) Supnick property. The result in this paper can be applied to the construction of ring networks with high reliability in case where the inverse Supnick property is naturally assumed.

Reviews

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