On the minimum average distance spanning tree of the hypercube

DOI10.1007/S10440-008-9215-5MaRDI QIDQ934836zbMATH OpenOpenAlexFDO

Authors Maurice Tchuente, Paulin Melatagia Yonta, Jean-Michel Nlong, Yves Denneulin

Publication date 30 July 2008

Published in Acta Applicandae Mathematicae (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10440-008-9215-5

zbMATH Keywords

1-move heuristicBinomial treeGreedy algorithmHypercubeLocal optimalityMinimum average distanceSpanning treeTorus

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80)

Recommendations

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

Cites work

• A Computational Approach to the Selection of an Optimal Network
• A conjecture on Wiener indices in combinatorial chemistry
• A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
• Approximation algorithms for the shortest total path length spanning tree problem
• Efficient methods for multiple sequence alignment with guaranteed error bounds
• Exact algorithms for minimum routing cost trees
• Exact and approximate algorithms for optimal network design
• scientific article; zbMATH DE number 1052827 (Why is no real title available?)
• scientific article; zbMATH DE number 1463394 (Why is no real title available?)
• scientific article; zbMATH DE number 890671 (Why is no real title available?)
• scientific article; zbMATH DE number 1445315 (Why is no real title available?)
• The complexity of the network design problem
• Wiener index of trees: Theory and applications
• Worst-Case Analysis of Network Design Problem Heuristics

Cited in

(8)

• On spanning tree congestion of graphs
• A survey of the all-pairs shortest paths problem and its variants in graphs
• Distance preserving subtrees in minimum average distance spanning trees
• On thek-ary hypercube tree and its average distance
• On the average distance of the hypercube tree
• scientific article; zbMATH DE number 1463394 (Why is no real title available?)
• On minimum average stretch spanning trees in grid graphs
• Minimum average congestion of enhanced and augmented hypercubes into complete binary trees

Describes a project that uses

Uses Software

• OCOTILLO

This page was built for publication: On the minimum average distance spanning tree of the hypercube

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