m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--mgr.tex16
1 files changed, 16 insertions, 0 deletions
diff --git a/mgr.tex b/mgr.tex
index 8b1ea5a..8005fd9 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -1285,6 +1285,22 @@ With our algorithm we get, ``for free'', an
answering on structures of bounded treewidth. Indeed, bounded treewidth
structures are MSO interpretable in trees in linear time \cite{courcelle1992}.
+\section{LCA closure question answering}
+
+In Section \ref{computing-closure} we showed that the following question answering
+problem
+\queryproblem{LCA closure question answering}{%
+ a tree $T$.
+}{%
+ given a set of tree vertices $S$, compute the LCA closure of $S$.
+}
+has an \qptime{$O(|T|)$}{$|S| \log |S|$} solution. An open question is whether
+this is an optimal solution. If the question answering step's complexity could
+be reduced to $O(|S|)$, MSO query answering on structures of bounded treewidth
+would then be known to be in \lineardelaylin. Or is there a lower bound on
+computing LCA closures in this setting, for example, would it be possible to
+reduce comparison sorting to computing LCA closures?
+
\printbibliography
\end{document}