Special Cases of the Minimum Spanning Tree Problem under Explorable Edge and Vertex Uncertainty

Corinna Marlene Mathwieser, Eranda Cela

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Number of pages18
JournalNetworks
Volume2024
Early online date11 Jan 2024
DOIs
Publication statusE-pub ahead of print - 11 Jan 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)

Fingerprint

Dive into the research topics of 'Special Cases of the Minimum Spanning Tree Problem under Explorable Edge and Vertex Uncertainty'. Together they form a unique fingerprint.

Cite this