Probabilistic models for the Steiner tree problem

DOI10.1002/NET.20346MaRDI QIDQ3057166zbMATH OpenOpenAlexFDO

Authors Vangelis Th. Paschos, Orestis A. Telelis, V. Zissimopoulos

Publication date 24 November 2010

Published in Networks (Search for Journal in Brave)

Full work available at URL https://basepub.dauphine.fr/handle/123456789/3700

zbMATH Keywords

graphcomplexityapproximationforestSteiner tree

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Automata, Languages and Programming
• On the probabilistic min spanning tree problem
• Steiner Forests on Stochastic Metric Graphs
• Stochastic Steiner Tree with Non-uniform Inflation
• Solving two-stage stochastic Steiner tree problems by two-stage branch-and-cut

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1445376 (Why is no real title available?)
• scientific article; zbMATH DE number 6469210 (Why is no real title available?)
• A General Approximation Technique for Constrained Forest Problems
• A branch and bound algorithm for the robust shortest path problem with interval data.
• A priori optimization for the probabilistic maximum independent set problem
• Approximation Algorithms for 2-Stage Stochastic Optimization Problems
• Boosted sampling
• Integer Programming and Combinatorial Optimization
• Introduction to Stochastic Programming
• Linear Programming Under Uncertainty
• On the complexity of a class of combinatorial optimization problems with uncertainty
• On the probabilistic minimum coloring and minimum \(k\)-coloring
• Robust Optimization of Large-Scale Systems
• The Probabilistic Minimum Vertex-covering Problem
• The probabilistic longest path problem
• The probabilistic minimum spanning tree problem
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks

Cited in

(11)

• LP Rounding Approximation Algorithms for Stochastic Network Design
• Comments on Bern's probabilistic results on rectilinear Steiner trees
• On the probabilistic min spanning tree problem
• Steiner Forests on Stochastic Metric Graphs
• The probabilistic minimum dominating set problem
• Risk models for the prize collecting Steiner tree problems with interval data
• Evolutionary model for the Steiner tree problem with flow-dependent weights
• Automata, Languages and Programming
• Estimates for the Syracuse problem via a probabilistic model
• Stochastic Steiner Tree with Non-uniform Inflation
• Solving two-stage stochastic Steiner tree problems by two-stage branch-and-cut

This page was built for publication: Probabilistic models for the Steiner tree problem

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