An explicit solution of a generalized optimum requirement spanning tree problem with a property related to Monge

An explicit solution of a generalized optimum requirement spanning tree problem with a property related to Monge

0.00 Avg rating0 Votes
Article ID: iaor20021361
Country: United Kingdom
Volume: 8
Issue: 3
Start Page Number: 259
End Page Number: 268
Publication Date: May 2001
Journal: International Transactions in Operational Research
Authors:
Abstract:

The paper considers a generalization of the optimum requirement spanning tree problem (ORST problem) first studied by Hu in 1974. Originally, ORST was regarded as a communication network of tree type with the minimum average cost, and it is obtained by the well-known Gomory–Hu algorithm when the degrees of vertices are not restricted. The ORST problem is generalized by (i) generalizing the objective function and (ii) imposing maximum degree constraints. The generalized ORST problem includes some practical problems, one of which is proposed in this paper, but is not efficiently solvable in general. However, I show that a particular tree (which is obtained by a sort of greedy algorithm but is explicitly definable) is a solution of the generalized problem when a certain practical condition is satisfied. The condition is closely related to the Monge property, which is originally discussed in the Hitchcock transportation problem, and is known to make some NP-hard problems efficiently solvable.

Reviews

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