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

DOI10.1002/NET.22204MaRDI QIDQ6196899zbMATH OpenWikidataFDO

Authors Eranda Çela

Publication date 15 March 2024

Published in Networks (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

online algorithmsrandomized algorithmscompetitive analysisspanning treecactus graphsexplorable uncertainty

Mathematics Subject Classification ID

Mathematical programming (90Cxx)

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.

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

Cites work

• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 7075885 (Why is no real title available?)
• scientific article; zbMATH DE number 7740865 (Why is no real title available?)
• Computing minimum spanning trees with uncertainty
• Computing shortest paths with uncertainty
• Minimum spanning tree under explorable uncertainty in theory and experiments
• Minimum spanning tree verification under uncertainty
• Query minimization under stochastic uncertainty
• Randomization Helps Computing a Minimum Spanning Tree under Uncertainty
• Scheduling with explorable uncertainty
• Spanning spiders and light-splitting switches
• The Minimum Cost Query Problem on Matroids with Uncertainty Areas.
• The robust knapsack problem with queries

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)