From c68fe5a45bcad9cf3bb94bd192bdc2bbbe5a07d1 Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Sat, 7 Aug 2021 15:13:50 -0400 Subject: Fixup query problem definitions --- mgr.tex | 13 +++++++------ 1 file changed, 7 insertions(+), 6 deletions(-) (limited to 'mgr.tex') diff --git a/mgr.tex b/mgr.tex index 9abfe49..f9ca98f 100644 --- a/mgr.tex +++ b/mgr.tex @@ -105,7 +105,7 @@ d \subsection{Least Common Ancestor} \queryproblem{% - Least Common Ancestor (LCA) + Least Common Ancestor (LCA) Queries }{% a tree $T$. }{% @@ -205,11 +205,12 @@ defines We can now reduce the problem to the following: -\queryproblem{Highest Marked Descendant on Path}{% - a tree $T$ with distinguished black vertices +\queryproblem{Highest Marked Descendant on Path Queries}{% + a tree $T$ with set $M \subseteq V(T)$ of marked vertices. }{% - given a vertex $x$, its descendant $y$, find the node $z$ that - is the highest black node on the path between $x$ and $y$ + given a vertex $x$, its descendant $y$, find the node $z \in M$ that + is the highest marked node on the path between $x$ and $y$, if such $z$ + exists. } We will build an index structure, constructible in linear time, that allows us @@ -220,7 +221,7 @@ Berkman and Vishkin for computing LCA queries. First, let's define an auxillary problem we will use, that of Range Minimum Queries (RMQ): -\queryproblem{Range Minimum Query}{% +\queryproblem{Range Minimum Queries}{% an array $A$ of integers. }{% given indices $i$ and $j$, return the index of the smallest -- cgit v1.2.3