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

Greedy algorithmTorusSpanning treeHypercube1-move heuristicBinomial treeLocal optimalityMinimum average distance

Mathematics Subject Classification ID

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

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

• 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?)
• A Computational Approach to the Selection of an Optimal Network
• A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
• A conjecture on Wiener indices in combinatorial chemistry
• 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
• The complexity of the network design problem
• Wiener index of trees: Theory and applications
• Worst-Case Analysis of Network Design Problem Heuristics

Cited in

(7)

• A survey of the all-pairs shortest paths problem and its variants in graphs
• On spanning tree congestion of graphs
• On thek-ary hypercube tree and its average distance
• Minimum average congestion of enhanced and augmented hypercubes into complete binary trees
• Distance preserving subtrees in minimum average distance spanning trees
• On the average distance of the hypercube tree
• On minimum average stretch spanning trees in grid graphs

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)