Showing cs.DSShow all
2 papers · 1 filter
cs.DS2021
Round-Competitive Algorithms for Uncertainty Problems with Parallel Queries
Thomas Erlebach, Michael Hoffmann, Murilo S. de Lima
The area of computing with uncertainty considers problems where some information about the input elements is uncertain, but can be obtained using queries. For example, instead of t…
cs.DS2008
Computing Minimum Spanning Trees with Uncertainty
Thomas Erlebach, Michael Hoffmann, Danny Krizanc +2
We consider the minimum spanning tree problem in a setting where information about the edge weights of the given graph is uncertain. Initially, for each edge of the graph only…