IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v21y1987i3p163-170.html
   My bibliography  Save this article

Exact and Heuristic Algorithms for the Optimum Communication Spanning Tree Problem

Author

Listed:
  • R. K. Ahuja

    (Indian Institute of Technology, Kanpur 208 016, India)

  • V. V. S. Murty

    (OMC Computers Ltd., Secunderabad, India)

Abstract

Network design problems have been widely investigated in the literature. In this paper, we study one such design problem, known as the Optimum Communication Spanning Tree (OCST) problem. We develop an exact algorithm based on the branch and bound approach and a heuristic algorithm to solve the problem. The branch and bound algorithm uses the lower planes recently developed by the authors. Reoptimization of subproblems is extensively used to reduce computation. The heuristic algorithm is a two-phase algorithm: tree-building algorithm and tree-improvement algorithm. These algorithms have been tested on randomly generated Euclidean and non-Euclidean problems and results of these investigations are described. The branch and bound algorithm is able to solve moderately large sized problems in reasonable time. The two-phase heuristic algorithm has produced excellent results by providing optimal solutions for all the problems tested. Further, it is capable of solving problems of size 100 nodes and 1,000 arcs in about 30 seconds on DEC 10.

Suggested Citation

  • R. K. Ahuja & V. V. S. Murty, 1987. "Exact and Heuristic Algorithms for the Optimum Communication Spanning Tree Problem," Transportation Science, INFORMS, vol. 21(3), pages 163-170, August.
    • Handle: RePEc:inm:ortrsc:v:21:y:1987:i:3:p:163-170
    DOI: 10.1287/trsc.21.3.163
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.21.3.163
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.21.3.163?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Richard Church & John Current, 1993. "Maximal covering tree problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 40(1), pages 129-142, February.
    2. Yogesh Kumar Agarwal & Prahalad Venkateshan, 2019. "New Valid Inequalities for the Optimal Communication Spanning Tree Problem," INFORMS Journal on Computing, INFORMS, vol. 31(2), pages 268-284, April.
    3. Li, Gang & Balakrishnan, Anantaram, 2016. "Models and algorithms for network reduction," European Journal of Operational Research, Elsevier, vol. 248(3), pages 930-942.
    4. Christian Tilk & Stefan Irnich, 2016. "Combined Column-and-Row-Generation for the Optimal Communication Spanning Tree Problem," Working Papers 1613, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    5. Ivan Contreras & Elena Fernández & Alfredo Marín, 2010. "Lagrangean bounds for the optimum communication spanning tree problem," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 18(1), pages 140-157, July.
    6. Hui Chen & Ann Melissa Campbell & Barrett W. Thomas, 2008. "Network design for time‐constrained delivery," Naval Research Logistics (NRL), John Wiley & Sons, vol. 55(6), pages 493-515, September.
    7. Zetina, Carlos Armando & Contreras, Ivan & Fernández, Elena & Luna-Mota, Carlos, 2019. "Solving the optimum communication spanning tree problem," European Journal of Operational Research, Elsevier, vol. 273(1), pages 108-117.
    8. Prabha Sharma, 2006. "Algorithms for the optimum communication spanning tree problem," Annals of Operations Research, Springer, vol. 143(1), pages 203-209, March.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ortrsc:v:21:y:1987:i:3:p:163-170. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.