{'fraction_non_alphanumeric': 0.017185821697099892, 'fraction_numerical': 0.0, 'mean_word_length': 4.861635220125786, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Adaptivity for Two Problems in Networks

An algorithm is said to be adaptive if it is capable of taking advantage of instance easiness; that is, it requires less computational resources for easier instances of the same size for the same problem. In this paper we explore adaptive algorithms for the Minimum Spanning Tree Problem and Shortest Path Problem in networks. We show that instance easiness in networks for these two problems is closely related to instance easiness in Sorting. In fact, we show that adaptivity depends on the capacity of the algorithm to adjust to the density of the underlying graph, the distance between the topological sorted order of the underlying graph and the order of proximity to the source node (measured by a measure of disorder), the cohesiveness of the graph (approximated by the degree sequence of the nodes), and the intrinsic diiculty in the network (evaluated as the number of bad cycles).