The probabilistic minimum spanning tree problem

DOI10.1002/NET.3230200302MaRDI QIDQ3481518zbMATH OpenOpenAlexFDO

Authors Dimitris Bertsimas

Publication date 1990

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.3230200302

zbMATH Keywords

a priori optimizationminimal expected lengthminimal spanning treeNP-hardprobabilistic variation

Mathematics Subject Classification ID

Trees (05C05) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Recommendations

• On the probabilistic min spanning tree problem
• Probabilistic Analysis of the Degree Bounded Minimum Spanning Tree Problem
• Stochastic minimum spanning trees and related problems
• Probabilistic analysis of an algorithm for the minimum spanning tree problem with diameter bounded below
• On the value of a random minimum spanning tree problem
• Stochastic bounded diameter minimum spanning tree problem
• On stochastic spanning tree problem
• The probabilistic minimum dominating set problem
• DEGREE-CONSTRAINED MINIMUM SPANNING TREE PROBLEM IN STOCHASTIC GRAPH
• The probabilistic min dominating set problem

Cited in

(31)

• The hybrid spanning tree problem
• Probabilistic combinatorial optimization problems on graphs: A new domain in operational research
• A two-level solution approach for solving the generalized minimum spanning tree problem
• The probabilistic minimum dominating set problem
• Genetic algorithm approach on multi-criteria minimum spanning tree problem
• Chance constrained bottleneck spanning tree problem
• Confidence regional method of stochastic spanning tree problem
• On the probabilistic min spanning tree problem
• On the chance-constrained minimum spanning \(k\)-core problem
• The generalized minimum spanning tree problem: an overview of formulations, solution procedures and latest advances
• Further results on the probabilistic traveling salesman problem
• Characterizing acyclic graphs by labeling edges
• On the probabilistic minimum coloring and minimum k-coloring
• DEGREE-CONSTRAINED MINIMUM SPANNING TREE PROBLEM IN STOCHASTIC GRAPH
• A survey on combinatorial optimization in dynamic environments
• Maximising the worth of nascent networks
• scientific article; zbMATH DE number 5931400 (Why is no real title available?)
• Probabilistic models for the Steiner tree problem
• A variation of the minimum spanning tree problem for the application to mathematical OCR
• Probabilistic analysis of an algorithm for the minimum spanning tree problem with diameter bounded below
• On the random 2-stage minimum spanning tree
• Path optimality conditions for minimum spanning tree problem with uncertain edge weights
• The Probabilistic Minimum Vertex-covering Problem
• Uncertain distribution-minimum spanning tree problem
• scientific article; zbMATH DE number 1444281 (Why is no real title available?)
• Stochastic minimum spanning trees and related problems
• Stochastic minimum spanning trees in Euclidean spaces
• Vertex-Uncertainty in Graph-Problems
• Stability analysis of the minimum spanning tree problem
• Network reliability: Heading out on the highway
• Probabilistic graph-coloring in bipartite and split graphs

This page was built for publication: The probabilistic minimum spanning tree problem

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