{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,13]],"date-time":"2025-11-13T07:17:48Z","timestamp":1763018268925,"version":"3.41.0"},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2020,11,8]],"date-time":"2020-11-08T00:00:00Z","timestamp":1604793600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/M508111\/1"],"award-info":[{"award-number":["EP\/M508111\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["ME 3825\/1"],"award-info":[{"award-number":["ME 3825\/1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2020,12,6]]},"abstract":"<jats:p>We consider the minimum spanning tree (MST) problem in an uncertainty model where interval edge weights can be explored to obtain the exact weight. The task is to find an MST by querying the minimum number of edges. This problem has received quite some attention from the algorithms theory community. In this article, we conduct the first practical experiments for MST under uncertainty, theoretically compare three known algorithms, and compare theoretical with practical behavior of the algorithms. Among others, we observe that the average performance and the absolute number of queries are both far from the theoretical worst-case bounds. Furthermore, we investigate a known general preprocessing procedure and develop an implementation thereof that maximally reduces the data uncertainty. We also characterize a class of instances that is solved to optimality by our preprocessing. Our experiments are based on practical data from an application in telecommunications and uncertainty instances generated from the standard TSPLib graph library.<\/jats:p>","DOI":"10.1145\/3422371","type":"journal-article","created":{"date-parts":[[2020,11,8]],"date-time":"2020-11-08T11:40:53Z","timestamp":1604835653000},"page":"1-20","source":"Crossref","is-referenced-by-count":5,"title":["Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments"],"prefix":"10.1145","volume":"25","author":[{"given":"Jacob","family":"Focke","sequence":"first","affiliation":[{"name":"University of Oxford, Oxford, UK"}]},{"given":"Nicole","family":"Megow","sequence":"additional","affiliation":[{"name":"University of Bremen, Bibliothekstra\u00dfe, Bremen, Germany"}]},{"given":"Julie","family":"Mei\u00dfner","sequence":"additional","affiliation":[{"name":"Technical University of Berlin, Berlin, Germany"}]}],"member":"320","published-online":{"date-parts":[[2020,11,8]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"Ahuja R. K.","year":"1993","unstructured":"R. K. Ahuja , T. L. Magnanti , and J. B. Orlin . 1993 . Network Flows: Theory, Algorithms, and Applications . Prentice Hall . R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. 1993. Network Flows: Theory, Algorithms, and Applications. Prentice Hall."},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"A. Ben-Tal L. El Ghaoui and A. S. Nemirovski. 2009. Robust Optimization. Princeton Series in Applied Mathematics. Princeton University Press.  A. Ben-Tal L. El Ghaoui and A. S. Nemirovski. 2009. Robust Optimization. Princeton Series in Applied Mathematics. Princeton University Press.","DOI":"10.1515\/9781400831050"},{"key":"e_1_2_1_3_1","unstructured":"J. R. Birge and F. Louveaux. 1997. Introduction to Stochastic Programming. Springer Series in Operations Research. Springer.  J. R. Birge and F. Louveaux. 1997. Introduction to Stochastic Programming. Springer Series in Operations Research. Springer."},{"key":"e_1_2_1_4_1","unstructured":"A. Borodin and R. El-Yaniv. 1998. Online Computation and Competitive Analysis. Cambridge University Press.  A. Borodin and R. El-Yaniv. 1998. Online Computation and Competitive Analysis. Cambridge University Press."},{"volume-title":"Proceedings of the International Workshop on Graph-Theoretic Concepts in Computer Science (WG\u201914)","author":"Erlebach T.","key":"e_1_2_1_5_1","unstructured":"T. Erlebach and M. Hoffmann . 2014. Minimum spanning tree verification under uncertainty . In Proceedings of the International Workshop on Graph-Theoretic Concepts in Computer Science (WG\u201914) . 164--175. DOI:10.1007\/978-3-319-12340-0_14 10.1007\/978-3-319-12340-0_14 T. Erlebach and M. Hoffmann. 2014. Minimum spanning tree verification under uncertainty. In Proceedings of the International Workshop on Graph-Theoretic Concepts in Computer Science (WG\u201914). 164--175. DOI:10.1007\/978-3-319-12340-0_14"},{"key":"e_1_2_1_6_1","unstructured":"T. Erlebach and M. Hoffmann. 2015. Query-competitive algorithms for computing with uncertainty. Bull. EATCS 116 (2015).  T. Erlebach and M. Hoffmann. 2015. Query-competitive algorithms for computing with uncertainty. Bull. EATCS 116 (2015)."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.11.025"},{"volume-title":"Proceedings of the Annual Symposium on Theoretical Aspects of Computer Science (STACS\u201908)","author":"Erlebach T.","key":"e_1_2_1_8_1","unstructured":"T. Erlebach , M. Hoffmann , D. Krizanc , M. Mihal\u00e1k , and R. Raman . 2008. Computing minimum spanning trees with uncertainty . In Proceedings of the Annual Symposium on Theoretical Aspects of Computer Science (STACS\u201908) . 277--288. DOI:10.4230\/LIPIcs.STACS.2008.1358 10.4230\/LIPIcs.STACS.2008.1358 T. Erlebach, M. Hoffmann, D. Krizanc, M. Mihal\u00e1k, and R. Raman. 2008. Computing minimum spanning trees with uncertainty. In Proceedings of the Annual Symposium on Theoretical Aspects of Computer Science (STACS\u201908). 277--288. DOI:10.4230\/LIPIcs.STACS.2008.1358"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.07.005"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701395668"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the International Symposium on Experimental Algorithms (SEA\u201917)","author":"Focke J.","year":"2017","unstructured":"J. Focke , N. Megow , J. Mei\u00dfner . 2017 . Minimum spanning tree under explorable uncertainty in theory and experiments . In Proceedings of the International Symposium on Experimental Algorithms (SEA\u201917) . 1--22. DOI:10.4230\/LIPIcs.SEA.2017.22 10.4230\/LIPIcs.SEA.2017.22 J. Focke, N. Megow, J. Mei\u00dfner. 2017. Minimum spanning tree under explorable uncertainty in theory and experiments. In Proceedings of the International Symposium on Experimental Algorithms (SEA\u201917). 1--22. DOI:10.4230\/LIPIcs.SEA.2017.22"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2014.09.010"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-015-9664-y"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103449"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1088375"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.3.4.376"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3422371","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3422371","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:03:21Z","timestamp":1750197801000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3422371"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,8]]},"references-count":16,"alternative-id":["10.1145\/3422371"],"URL":"https:\/\/doi.org\/10.1145\/3422371","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2020,11,8]]}}}