Search

Traffic congestion occurs frequently in urban settings, and is not always caused by traffic incidents. In this paper, we propose a simple method for detecting traffic incidents from probe-car data by identifying unusual events that distinguish incidents from spontaneous congestion. First, we introduce a traffic state model based on a probabilistic topic model to describe the traffic states for a variety of roads. Formulas for estimating the model parameters are derived, so that the model of usual traffic can be learned using an expectation–maximization algorithm. Next, we propose several divergence functions to evaluate differences between the current and usual traffic states and streaming algorithms that detect high-divergence segments in real time. We conducted an experiment with data collected for the entire Shuto Expressway system in Tokyo during 2010 and 2011. The results showed that our method discriminates successfully between anomalous car trajectories and the more usual, slowly moving traffic patterns. [ABSTRACT FROM AUTHOR]

Abstract: The edit distance problem for rooted unordered trees is known to be NP-hard. Based on this fact, this paper studies exponential-time algorithms for the problem. For a general case, an time algorithm is presented, where and are the numbers of nodes and and are the numbers of branching nodes in two input trees. This algorithm is obtained by a combination of dynamic programming, exhaustive search, and maximum weighted bipartite matching. For bounded degree trees over a fixed alphabet, it is shown that the problem can be solved in time for any fixed . This result is achieved by avoiding duplicate calculations for identical subsets of small subtrees. [Copyright &y& Elsevier]

This article studies the parameterized complexity of the unification problem with associative, commutative, or associative-commutative functions with respect to the parameter “number of variables”. It is shown that if every variable occurs only once then both of the associative and associative-commutative unification problems can be solved in polynomial time, but that in the general case, both problems are W [ 1 ] -hard even when one of the two input terms is variable-free. For commutative unification, an algorithm whose time complexity depends exponentially on the number of variables is presented; moreover, if a certain conjecture is true then the special case where one input term is variable-free belongs to FPT. Some related results are also derived for a natural generalization of the classic string and tree edit distance problems that allows variables. [ABSTRACT FROM AUTHOR]

The tree inclusion problem is, given two node-labeled trees P and T (the "pattern tree" and the "target tree"), to locate every minimal subtree in T (if any) that can be obtained by applying a sequence of node insertion operations to P. Although the ordered tree inclusion problem is solvable in polynomial time, the unordered tree inclusion problem is NP-hard. The currently fastest algorithm for the latter is a classic algorithm by Kilpeläinen and Mannila from 1995 that runs in O (d 2 2 d m n) time, where m and n are the sizes of the pattern and target trees, respectively, and d is the degree of the pattern tree. Here, we develop a new algorithm that runs in O (d 2 d m n 2) time, improving the exponential factor from 2 2 d to 2 d by considering a particular type of ancestor-descendant relationships that is suitable for dynamic programming. We also study restricted variants of the unordered tree inclusion problem. • We present an O ⁎ (2 d) -time algorithm for the unordered tree inclusion problem. • This is the first improvement since the O ⁎ (4 d) -time algorithm from 1995 by Kilpeläinen and Mannila. • Even faster algorithms are given for some versions of the problem with restrictions on the node labels and tree heights. • A special case of the problem where only the leaves have distinct labels is proved to be NP-hard. [ABSTRACT FROM AUTHOR]