Randomization Helps Computing a Minimum Spanning Tree under Uncertainty

DOI10.1007/978-3-662-48350-3_73zbMath1466.68084OpenAlexW2737307554WikidataQ57399737 ScholiaQ57399737MaRDI QIDQ3452848

Julie Meißner, Nicole Megow, 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

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

Related Items (3)

Unnamed Item ⋮ Algorithms for Queryable Uncertainty ⋮ Randomization Helps Computing a Minimum Spanning Tree under Uncertainty

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The robust knapsack problem with queries
• The update complexity of selection and related problems
• Query-Competitive Algorithms for Cheapest Set Problems under Uncertainty
• Minimum Spanning Tree Verification Under Uncertainty
• Computing shortest paths with uncertainty
• Two-sided Online Bipartite Matching and Vertex Cover: Beating the Greedy Algorithm
• Introduction to Stochastic Programming
• Computing the Median with Uncertainty
• Combinatorial optimization. Theory and algorithms.

This page was built for publication: Randomization Helps Computing a Minimum Spanning Tree under Uncertainty