Balancing minimum spanning trees and multiple-source minimum routing cost spanning trees on metric graphs

DOI10.1016/j.ipl.2005.11.021zbMath1184.05125OpenAlexW2014991506MaRDI QIDQ845678

Chung-Ming Lin, Chuan Yi Tang, Yin Te Tsai

Publication date: 29 January 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2005.11.021

zbMATH Keywords

MSTgraph algorithmsminimum spanning treebuilding costminimum routing cost spanning treeMRCSTmultiple-source routing cost

Mathematics Subject Classification ID

Trees (05C05) Network design and communication in computer systems (68M10) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• A note on two problems in connexion with graphs
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Approximation algorithms for some optimum communication spanning tree problems
• Balancing minimum spanning trees and shortest-path trees
• The complexity of the network design problem
• Light graphs with small routing cost
• On the History of the Minimum Spanning Tree Problem
• A polynomial time approximation scheme for the two-source minimum routing cost spanning trees
• A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees

This page was built for publication: Balancing minimum spanning trees and multiple-source minimum routing cost spanning trees on metric graphs