On the probabilistic min spanning tree problem

DOI10.1007/s10852-011-9165-1zbMath1382.05066OpenAlexW2117879716MaRDI QIDQ1935723

Nicolas Boria, Cécile Murat, Vangelis Th. Paschos

Publication date: 19 February 2013

Published in: JMMA. Journal of Mathematical Modelling and Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10852-011-9165-1

zbMATH Keywords

complexityapproximationspanning treeprobabilistic optimization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Combinatorial probability (60C05) Approximation algorithms (68W25)

Related Items

A survey on combinatorial optimization in dynamic environments ⋮ The probabilistic minimum dominating set problem ⋮ A priori TSP in the Scenario Model ⋮ A priori TSP in the scenario model

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Local search for the probabilistic traveling salesman problem: correction to the 2-p-opt and 1-shift algorithms
• Probabilistic graph-coloring in bipartite and split graphs
• An \(0(| E|\log\log| V|)\) algorithm for finding minimum spanning trees
• Robust discrete optimization and its applications
• Arborescence optimization problems solvable by Edmonds' algorithm
• On the probabilistic minimum coloring and minimum \(k\)-coloring
• Combinatorial optimization. Theory and applications.
• Linear Programming under Uncertainty
• Probabilistic models for the Steiner Tree problem
• The probabilistic minimum spanning tree problem
• Steiner Forests on Stochastic Metric Graphs
• A Priori Solution of a Traveling Salesman Problem in Which a Random Subset of the Customers Are Visited
• Shortest path problems with node failures
• Efficiency of a Good But Not Linear Set Union Algorithm
• Finding Minimum Spanning Trees
• The probabilistic longest path problem
• Probabilistic a priori routing-location problems
• Introduction to Stochastic Programming
• A minimum spanning tree algorithm with inverse-Ackermann type complexity
• The Probabilistic Minimum Vertex-covering Problem
• Traveling Salesman Facility Location Problems
• Optimum branchings
• A Priori Optimization
• A priori optimization for the probabilistic maximum independent set problem