Randomization helps computing a minimum spanning tree under uncertainty

DOI10.1007/978-3-662-48350-3_73MaRDI QIDQ3452848zbMATH OpenOpenAlexWikidataFDO

Authors Nicole Megow, Julie Meißner, Martin Skutella

Publication date 19 November 2015

Published in Algorithms - ESA 2015 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-48350-3_73

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27) Analysis of algorithms (68W40)

Recommendations

• Randomization Helps Computing a Minimum Spanning Tree under Uncertainty
• Computing minimum spanning trees with uncertainty
• Minimum spanning tree under explorable uncertainty in theory and experiments
• Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments
• Minimum spanning tree verification under uncertainty

Cites work

• Combinatorial optimization. Theory and algorithms.
• Computing minimum spanning trees with uncertainty
• Computing shortest paths with uncertainty
• Computing the Median with Uncertainty
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• Introduction to Stochastic Programming
• Minimum spanning tree verification under uncertainty
• Query-competitive algorithms for cheapest set problems under uncertainty
• Robust optimization
• The robust knapsack problem with queries
• The update complexity of selection and related problems
• Two-sided online bipartite matching and vertex cover: beating the greedy algorithm

Cited in

(12)

• Query-competitive algorithms for cheapest set problems under uncertainty
• Minimum spanning tree verification under uncertainty
• Minimum spanning tree under explorable uncertainty in theory and experiments
• Algorithms for queryable uncertainty
• Computing minimum spanning trees with uncertainty
• Scheduling with explorable uncertainty
• The Minimum Cost Query Problem on Matroids with Uncertainty Areas.
• Randomization Helps Computing a Minimum Spanning Tree under Uncertainty
• scientific article; zbMATH DE number 5658688 (Why is no real title available?)
• Query minimization under stochastic uncertainty
• Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments
• Query-competitive algorithms for cheapest set problems under uncertainty

This page was built for publication: Randomization helps computing a minimum spanning tree under uncertainty

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