The probabilistic minimum spanning tree problem

DOI10.1002/net.3230200302zbMath0702.90089OpenAlexW2120881403MaRDI QIDQ3481518

Dimitris J. 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

NP-hardminimal spanning treea priori optimizationminimal expected lengthprobabilistic variation

Mathematics Subject Classification ID

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

Related Items

The hybrid spanning tree problem ⋮ Further results on the probabilistic traveling salesman problem ⋮ Maximising the worth of nascent networks ⋮ A survey on combinatorial optimization in dynamic environments ⋮ Probabilistic analysis of an algorithm for the minimum spanning tree problem with diameter bounded below ⋮ A two-level solution approach for solving the generalized minimum spanning tree problem ⋮ Probabilistic combinatorial optimization problems on graphs: A new domain in operational research ⋮ The probabilistic minimum dominating set problem ⋮ On the probabilistic min spanning tree problem ⋮ Network reliability: Heading out on the highway ⋮ Characterizing acyclic graphs by labeling edges ⋮ On the probabilistic minimum coloring and minimum \(k\)-coloring ⋮ Probabilistic models for the Steiner Tree problem ⋮ The generalized minimum spanning tree problem: an overview of formulations, solution procedures and latest advances ⋮ Probabilistic graph-coloring in bipartite and split graphs ⋮ Genetic algorithm approach on multi-criteria minimum spanning tree problem ⋮ Vertex-Uncertainty in Graph-Problems

Cites Work

• Unnamed Item