On the minimum average distance spanning tree of the hypercube

DOI10.1007/S10440-008-9215-5zbMATH Open1155.05056OpenAlexW2037653778MaRDI QIDQ934836FDOQ934836

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

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

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)

Cites Work

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

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

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)