Tootfinder

Approximate Cartesian Tree Matching with Substitutions
Panagiotis Charalampopoulos, Jonas Ellert, Manal Mohamed
https://arxiv.org/abs/2602.08570 https://arxiv.org/pdf/2602.08570 https://arxiv.org/html/2602.08570
arXiv:2602.08570v1 Announce Type: new
Abstract: The Cartesian tree of a sequence captures the relative order of the sequence's elements. In recent years, Cartesian tree matching has attracted considerable attention, particularly due to its applications in time series analysis. Consider a text $T$ of length $n$ and a pattern $P$ of length $m$. In the exact Cartesian tree matching problem, the task is to find all length-$m$ fragments of $T$ whose Cartesian tree coincides with the Cartesian tree $CT(P)$ of the pattern. Although the exact version of the problem can be solved in linear time [Park et al., TCS 2020], it remains rather restrictive; for example, it is not robust to outliers in the pattern.
To overcome this limitation, we consider the approximate setting, where the goal is to identify all fragments of $T$ that are close to some string whose Cartesian tree matches $CT(P)$. In this work, we quantify closeness via the widely used Hamming distance metric. For a given integer parameter $k>0$, we present an algorithm that computes all fragments of $T$ that are at Hamming distance at most $k$ from a string whose Cartesian tree matches $CT(P)$. Our algorithm runs in time $\mathcal O(n \sqrt{m} \cdot k^{2.5})$ for $k \leq m^{1/5}$ and in time $\mathcal O(nk^5)$ for $k \geq m^{1/5}$, thereby improving upon the state-of-the-art $\mathcal O(nmk)$-time algorithm of Kim and Han [TCS 2025] in the regime $k = o(m^{1/4})$.
On the way to our solution, we develop a toolbox of independent interest. First, we introduce a new notion of periodicity in Cartesian trees. Then, we lift multiple well-known combinatorial and algorithmic results for string matching and periodicity in strings to Cartesian tree matching and periodicity in Cartesian trees.
toXiv_bot_toot

How did the Urban Network Flow Adapt to the Collapse of the Carola Bridge?
Jyotirmaya Ijaradar, Ning Xie, Lei Wei, Sebastian Pape, Matthias K\"orner, Meng Wang
https://arxiv.org/abs/2603.19947 https://arxiv.org/pdf/2603.19947 https://arxiv.org/html/2603.19947
arXiv:2603.19947v1 Announce Type: new
Abstract: The unexpected collapse of the Carola Bridge in Dresden, Germany, provides a rare opportunity to characterise how urban network traffic adapts to an unexpected infrastructure disruption. This study develops a data-driven analytical framework using traffic data from the Dresden traffic management system to assess the short-term impacts of the disruption. By combining statistical comparisons of pre- and post-collapse motorised traffic distributions, peak-hour shifts, and Park-and-Ride data analyses, the framework reveals how traffic dynamics and traveller choices adjust under infrastructure disruption. Results reveal that the two closest bridges, the Albert and Marien Bridges, absorb the majority of the diverted motorised traffic. In particular, the daily traffic volume on the Albert bridge increases by up to 81%, which is equivalent to 3.5 hours of traffic operating with maximum flow. Peak hours on critical links are significantly prolonged, reaching up to 250 minutes. Besides redistribution, the overall daily motorised traffic crossing the Elbe river declines by approximately 8,000 vehicles, while Park-and-Ride usage increases by up to 188%, suggesting a potential travel mode shift after the disruption. The study reveals the patterns of traffic redistribution following an unexpected disruption and provides insights for resilience planning and emergency traffic management.
toXiv_bot_toot