MAD trees and distance-hereditary graphs

DOI10.1016/S0166-218X(02)00422-5zbMath1022.05023OpenAlexW2039281020MaRDI QIDQ1408821

Wayne Goddard, Peter Dankelmann, Elias Dahlhaus, Henda C. Swart

Publication date: 25 September 2003

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(02)00422-5

zbMATH Keywords

spanning treeminimum average distance

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (9)

A survey of the all-pairs shortest paths problem and its variants in graphs ⋮ On the intercluster distance of a tree metric ⋮ The complexity of minimizing certain cost metrics for \(k\)-source spanning trees. ⋮ Multi-source spanning trees: Algorithms for minimizing source eccentricities. ⋮ Spanning trees: A survey ⋮ Combinatorial network abstraction by trees and distances ⋮ The zoo of tree spanner problems ⋮ A linear-time algorithm to compute a MAD tree of an interval graph ⋮ Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Completely separable graphs
• Distance-hereditary graphs
• Computing the average distance of an interval graph
• Extremal values for ratios of distances in trees
• Linear time solvable optimization problems on graphs of bounded clique-width
• Average distance in colored graphs
• Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
• Decomposition of Directed Graphs
• A CHARACTERIZATION OF DISTANCE-HEREDITARY 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: MAD trees and distance-hereditary graphs