A linear-time algorithm to compute a MAD tree of an interval graph

DOI10.1016/j.ipl.2003.11.009zbMath1183.68415OpenAlexW1971402194MaRDI QIDQ1029091

Elias Dahlhaus, R. Ravi, Peter Dankelmann

Publication date: 9 July 2009

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

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

zbMATH Keywords

spanning treegraph algorithmsinterval graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (4)

On the minimum routing cost clustered tree problem ⋮ A survey of the all-pairs shortest paths problem and its variants in graphs ⋮ On the intercluster distance of a tree metric ⋮ Spanning trees: A survey

Cites Work

• Computing the average distance of an interval graph
• Extremal values for ratios of distances in trees
• MAD trees and distance-hereditary graphs
• Average distance in colored graphs
• The complexity of the network design problem
• A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees

This page was built for publication: A linear-time algorithm to compute a MAD tree of an interval graph