On the value of a random minimum spanning tree problem
From MaRDI portal
Publication:1066149
DOI10.1016/0166-218X(85)90058-7zbMath0578.05015WikidataQ56484417 ScholiaQ56484417MaRDI QIDQ1066149
Publication date: 1985
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Related Items
Partition Functions of Discrete Coalescents: From Cayley’s Formula to Frieze’s ζ(3) Limit Theorem, On Frieze's \(\zeta\) (3) limit for lengths of minimal spanning trees, Approximating the Expected Values for Combinatorial Optimization Problems over Stochastic Points, The Random QUBO, THE NEAREST UNVISITED VERTEX WALK ON RANDOM GRAPHS, All-pairs shortest paths and the essential subgraph, A survey on combinatorial optimization in dynamic environments, Note on the structure of Kruskal's algorithm, Asymptotically optimal approach to the approximate solution of several problems of covering a graph by nonadjacent cycles, On the longest path of a randomly weighted tournament, A concentration inequality for the facility location problem, GHS algorithm on a graph with random weights, The mean field traveling salesman and related problems, Successive minimum spanning trees, On asymptotically optimal approach for finding of the minimum total weight of edge-disjoint spanning trees with a given diameter, Multidimensional Lambert-Euler inversion and vector-multiplicative coalescent processes, Weak disorder asymptotics in the stochastic mean-field model of distance, Unnamed Item, Models of random subtrees of a graph, Geometry of the minimal spanning tree in the heavy-tailed regime: new universality classes, On the Length of a Random Minimum Spanning Tree, Replica symmetry of the minimum matching, Minimum Cost Matching in a Random Graph with Random Costs, Bounds for Random Binary Quadratic Programs, Weak disorder in the stochastic mean-field model of distance. II, Diameter of the Stochastic Mean-Field Model of Distance, Maximal Steiner Trees in the Stochastic Mean-Field Model of Distance, A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks, Tail bound for the minimal spanning tree of a complete graph., On random minimum length spanning trees, Minimum-weight combinatorial structures under random cost-constraints, A randomly weighted minimum spanning tree with a random cost constraint, Belief propagation for optimal edge cover in the random complete graph, A simple randomized scheme for constructing low-weight \(k\)-connected spanning subgraphs with applications to distributed algorithms, Renewal sequences and record chains related to multiple zeta sums, Spanning-Tree Games., On the Difference of Expected Lengths of Minimum Spanning Trees, On Edge-Disjoint Spanning Trees in a Randomly Weighted Complete Graph, Central limit theorems for combinatorial optimization problems on sparse Erdős-Rényi graphs, Local tail bounds for functions of independent random variables, The ?(2) limit in the random assignment problem, Limit theorems for random cubical homology, Efficient algorithms for three‐dimensional axial and planar random assignment problems, A survey of max-type recursive distributional equations, Asymptotics of integrals of Betti numbers for random simplicial complex processes, Critical random graphs and the structure of a minimum spanning tree, Weight of a link in a shortest path tree and the Dedekind Eta function, Edge flows in the complete random-lengths network, On finding a minimum spanning tree in a network with random weights, Extremal paths in inhomogenous random graphs, Sorting and Selection with Random Costs, Geometry of the minimal spanning tree of a random 3-regular graph, Cross-Multiplicative Coalescent Processes and Applications, Successive shortest paths in complete graphs with random edge weights, On the greedy algorithm with random costs, On the rank of a random binary matrix, Asymptotic behavior of lifetime sums for random simplicial complex processes, Minimum weight disk triangulations and fillings, Typical values of extremal-weight combinatorial structures with independent symmetric weights, On asymptotically optimal approach for the problem of finding several edge-disjoint spanning trees of given diameter in an undirected graph with random edge weights, Gaussian tail for empirical distributions of MST on random graphs
Cites Work
