Special cases of the minimum spanning tree problem under explorable edge and vertex uncertainty

DOI10.1002/NET.22204arXiv2211.15611WikidataQ130202040 ScholiaQ130202040MaRDI QIDQ6196899FDOQ6196899

Authors: Eranda Çela 

Publication date: 15 March 2024

Published in: Networks (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/2211.15611

Recommendations

• Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments
• Minimum spanning tree under explorable uncertainty in theory and experiments
• Computing minimum spanning trees with uncertainty
• Path optimality conditions for minimum spanning tree problem with uncertain edge weights
• Uncertain distribution-minimum spanning tree problem

zbMATH Keywords

online algorithmsrandomized algorithmscompetitive analysisspanning treecactus graphsexplorable uncertainty

Mathematics Subject Classification ID

Mathematical programming (90Cxx)

Cites Work

• Title not available (Why is that?)
• Computing minimum spanning trees with uncertainty
• The robust knapsack problem with queries
• Spanning spiders and light-splitting switches
• Computing shortest paths with uncertainty
• Title not available (Why is that?)
• Scheduling with explorable uncertainty
• Randomization Helps Computing a Minimum Spanning Tree under Uncertainty
• Minimum spanning tree under explorable uncertainty in theory and experiments
• Minimum spanning tree verification under uncertainty
• The Minimum Cost Query Problem on Matroids with Uncertainty Areas.
• Query minimization under stochastic uncertainty
• Title not available (Why is that?)

This page was built for publication: Special cases of the minimum spanning tree problem under explorable edge and vertex uncertainty

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6196899)