7 citations · 7 across the 1 of their papers we have counts for
3 papers
Orienting (hyper)graphs under explorable stochastic uncertainty
Evripidis Bampis, Christoph Dürr, Thomas Erlebach +3
Given a hypergraph with uncertain node weights following known probability distributions, we study the problem of querying as few nodes as possible until the identity of a node wit…
An Adversarial Model for Scheduling with Testing
Christoph Dürr, Thomas Erlebach, Nicole Megow +1
We introduce a novel adversarial model for scheduling with explorable uncertainty. In this model, the processing time of a job can potentially be reduced (by an a priori unknown am…
Quantum query complexity of graph connectivity
Christoph Durr, Mehdi Mhalla, Yaohui Lei
Harry Buhrman et al gave an Omega(sqrt n) lower bound for monotone graph properties in the adjacency matrix query model. Their proof is based on the polynomial method. However for…