diff options
author | Marcin Chrzanowski <mc370754@students.mimuw.edu.pl> | 2021-12-16 17:04:19 +0100 |
---|---|---|
committer | Marcin Chrzanowski <mc370754@students.mimuw.edu.pl> | 2021-12-16 17:04:19 +0100 |
commit | 27c1d117c45622c462f11b648cab1c1d185263f4 (patch) | |
tree | 6426f7fc87cc59aa4298eb926a51d7a11f5c984d | |
parent | 4285da4999acaa2bca23148e91e1f184dc72415d (diff) |
Small improvement in introduction
-rw-r--r-- | mgr.tex | 10 |
1 files changed, 5 insertions, 5 deletions
@@ -98,11 +98,11 @@ single tree and formula, varying the valuations we ask about, and thus allow a preprocessing step over the formula and tree. In this case, the above naive algorithm could be improved with Amarilli et al.'s \cite{amarilli2019} data structure that allows updates of the underlying tree. Let $m$ be the size of a -given question, i.e. $|W_1 \cup ... \cup W_k|$. Amarilli's result allows us to -preprocess the tree in linear time, label it with a choice of $W_1, \ldots, W_k$ -in time $O(m \log n)$, then answer model checking in constant time, thus greatly -improving over the naive algorithm for questions that talk about a small number -of vertices compared to the size of the whole tree. +given question, i.e. $m = |W_1 \cup \ldots \cup W_k|$. Amarilli's result allows +us to preprocess the tree in linear time, label it with a choice of $W_1, +\ldots, W_k$ in time $O(m \log n)$, then answer model checking in constant time, +thus greatly improving over the naive algorithm for questions that talk about a +small number of vertices compared to the size of the whole tree. \section{Main result} |