Abstract
This article studies the Minimum Spanning Tree Problem under Explorable Uncertainty as well as a related vertex uncertainty version of the problem. We particularly consider special instance types, including cactus graphs, for which we provide randomized algorithms. We introduce the problem of finding a minimum weight spanning star under uncertainty for which we show that no algorithm can achieve constant competitive ratio.
| Original language | English |
|---|---|
| Pages (from-to) | 587-604 |
| Number of pages | 18 |
| Journal | Networks |
| Volume | 83 |
| Issue number | 3 |
| Early online date | 11 Jan 2024 |
| DOIs | |
| Publication status | Published - Apr 2024 |
Keywords
- cs.DS
- cs.DM
- math.OC
- explorable uncertainty
- randomized algorithms
- spanning tree
- cactus graphs
- online algorithms
- competitive analysis
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Theoretical Computer Science
- Information Systems
- Computer Networks and Communications
Fields of Expertise
- Information, Communication & Computing
Treatment code (Nähere Zuordnung)
- Basic - Fundamental (Grundlagenforschung)