English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

The Capacitated Minimum Spanning Tree Problem (CMSTP) is to find a minimum spanning tree subject to an additional constraint stating that the number of nodes in each subtree pending from a given root node is not greater than a given number Q. Gouveia and Martins (1996) proposed a hop-indexed flow model for the CMSTP. This formulation is a generalization of a wellknown single-commodity flow model proposed by Gavish (1983). The linear programming (LP) bound of the new formulation has produced the best bounds for a set of tests (tests with the root in the corner of the grid of nodes) which have been characterized as hard by most of the available lower-bounding schemes. The deficiency of the new formulation is the range of variation of the extra hop index which leads to storage problems when instances with 80 nodes are tried. We propose several levels of aggregation of the original formulation, yielding a hierarchy of hop-indexed LP models with fewer variables than the original model and which are weaker than the LP relaxation of the original formulation but still stronger than the LP relaxation of the single-commodity flow model. This hierarchy suggests an iterative method for computing lower bounds for the CMSTP. It iteratively transforms a given model into a more disaggregated model with a tighter relaxation. Reduction tests performed in a given iteration can be used to eliminate variables from the models arising in later iterations. Computational results assessing the efficiency of the iterative method are reported. The results are taken from a set of benchmark instances with 41 and 81 nodes and two new instances with 121 nodes. © 2000 John Wiley & Sons, Inc.

A hierarchy of hop-indexed models for the Capacitated Minimum Spanning Tree Problem