On the probabilistic min spanning tree problem
From MaRDI portal
Publication:1935723
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
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
