On finding most uniform spanning trees

DOI10.1016/0166-218X(88)90062-5MaRDI QIDQ1102979zbMATH OpenFDO

Authors Baruch Schieber, Zvi Galil

Publication date 1988

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218X(88)90062-5

zbMATH Keywords

algorithmspanning treeweighted graph

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10)

Review text

The most uniform spanning tree of a graph with real valued weights assigned to its edges is a spanning tree with the minimal difference between the most and least weighted edges. The paper describes an O(m log n) algorithm for finding such spanning trees (m and n denote the number of edges and vertices respectively.

Recommendations

• Most and least uniform spanning trees
• Uniform spanning trees on Sierpiński graphs
• scientific article; zbMATH DE number 953290
• Choosing a spanning tree for the integer lattice uniformly
• On finding spanning trees with few leaves
• On the SPANNING k-TREE problem
• scientific article; zbMATH DE number 1123757
• An almost-linear time algorithm for uniform random spanning tree generation
• scientific article; zbMATH DE number 4156450

Cites work

• A data structure for dynamic trees
• scientific article; zbMATH DE number 65738 (Why is no real title available?)
• Most and least uniform spanning trees

Cited in

(24)

• Most and least uniform spanning trees
• An O(m n) algorithm for the max+sum spanning tree problem
• Minimum dispersion problems
• Lexicographic balanced optimization problems
• The minimum labeling spanning trees
• Ordered weighted average optimization in multiobjective spanning tree problem
• Constrained balanced optimization problems
• The quadratic balanced optimization problem
• Finding the seed of uniform attachment trees
• Fairest edge usage and minimum expected overlap for random spanning trees
• Balanced Optimization with Vector Costs
• On discrete optimization with ordering
• scientific article; zbMATH DE number 496232 (Why is no real title available?)
• scientific article; zbMATH DE number 7238975 (Why is no real title available?)
• Rooted Uniform Monotone Minimum Spanning Trees
• Computational methods for logistics problems related to optimal trees
• Quadratic bottleneck problems
• High Spies (or How to Win a Programming Contest)
• Uniform tree approximation by global optimization techniques
• A branch-and-cut algorithm for the balanced traveling salesman problem
• The balanced traveling salesman problem
• Computing fair and bottleneck matchings in geometric graphs
• Robust balanced optimization
• An inverse model for the most uniform problem

This page was built for publication: On finding most uniform spanning trees

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