Output details
11 - Computer Science and Informatics
University of Leicester
Return to search
Output 0 of 0 in the submission
Output title
Computing Minimum Spanning Trees with Uncertainty
Type
E - Conference contribution
DOI
-
Name of conference/published proceedings
Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008, Bordeaux, France)
Volume number
-
Issue number
-
First page of article
277
ISSN of proceedings
-
Year of publication
2008
URL
-
Number of additional authors
4
Additional information
<12>This paper studies the Minimum Spanning Tree problem (MSTP) in a setting where the information about the edge weights is uncertain; such situations are of increasing practical significance. There are numerous ways of modelling this kind of uncertainty (cf. Suri's invited talk at ALGOSENSORS'12) and the update-competitive framework is one such, which is quite different from the above formulations. It has inspired follow-up work by Gupta et al [FSTTCS'11] in this model, and authors have published subsequent work on related models such as the input-thrifty framework of Bereg and Kirkpatrick [ISAAC'11].
Interdisciplinary
-
Cross-referral requested
-
Research group
None
Citation count
0
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-