On the minimum average distance spanning tree of the hypercube

DOI10.1007/s10440-008-9215-5zbMath1155.05056OpenAlexW2037653778MaRDI QIDQ934836

Jean-Michel Nlong, Paulin Melatagia Yonta, Maurice Tchuente, 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

HypercubeGreedy algorithmTorusSpanning tree1-move heuristicBinomial treeLocal optimalityMinimum average distance

Mathematics Subject Classification ID

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

Related Items (4)

A survey of the all-pairs shortest paths problem and its variants in graphs ⋮ On thek-ary hypercube tree and its average distance ⋮ On spanning tree congestion of graphs ⋮ DISTANCE PRESERVING SUBTREES IN MINIMUM AVERAGE DISTANCE SPANNING TREES

Uses Software

• OCOTILLO

Cites Work

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

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