{'fraction_non_alphanumeric': 0.020765027322404372, 'fraction_numerical': 0.006557377049180328, 'mean_word_length': 4.420118343195266, '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}}
Lower bounds for linear interval routing

Linear interval routing is a space-efficient routing method for point-to-point communication networks. It is a restricted variant of interval routing where the routing range associated with every link is represented by an interval with no wraparound. A common way to measure the efficiency of such routing methods is in terms of the maximal length of a path a message traverses. For interval routing, the upper bound and lower bound on this quantity are 2D and 2D - 3, respectively, where D is the diameter of the network. We prove a lower bound of Ω(D 2 ) on the length of a path a message traverses under linear interval routing. We further extend the result by showing a connection between the efficiency of linear interval routing and the total 2 -diameter (defined in Section 4) of the network, and by presenting a family of graphs for which this lower bound is tight.