Distance preserving subtrees in minimum average distance spanning trees

DOI10.1142/S1793830913500109MaRDI QIDQ2864852zbMATH OpenOpenAlexFDO

Authors Laurent Lyaudet, Paulin Melatagia Yonta, Maurice Tchuente, R. Ndoundam

Publication date 26 November 2013

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s1793830913500109

zbMATH Keywords

distance preservingminimum average distance spanning treeundirected graph

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12) Structural characterization of families of graphs (05C75)

Recommendations

• scientific article; zbMATH DE number 1463394
• On minimum average stretch spanning trees in grid graphs
• scientific article; zbMATH DE number 890671
• MAD trees and distance-hereditary graphs
• A linear-time algorithm to compute a MAD tree of an interval graph

Cites work

• A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
• Approximation algorithms for the shortest total path length spanning tree problem
• On the minimum average distance spanning tree of the hypercube
• Worst-Case Analysis of Network Design Problem Heuristics

Cited in

(8)

• MAD trees and distance-hereditary graphs
• Average distances on substitution trees
• Minimizing branching vertices in distance-preserving subgraphs
• Extremal distances for subtree transfer operations in binary trees
• Characterization of the distance between subtrees of a tree by the associated tight span
• scientific article; zbMATH DE number 1463394 (Why is no real title available?)
• scientific article; zbMATH DE number 890671 (Why is no real title available?)
• Parameterized algorithms for computing MAD trees

This page was built for publication: Distance preserving subtrees in minimum average distance spanning trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2864852)