From e09410a14cee2ac5a6e415a4fc8233edcecdf82f Mon Sep 17 00:00:00 2001
From: Gloria Mundi <gloria@gloria-mundi.eu>
Date: Tue, 27 Feb 2024 13:04:43 +0100
Subject: add binary lifting and make old LCA optional

---
 graph/graph.tex | 12 +++++++++++-
 1 file changed, 11 insertions(+), 1 deletion(-)

(limited to 'graph/graph.tex')

diff --git a/graph/graph.tex b/graph/graph.tex
index 6fbdb74..b251278 100644
--- a/graph/graph.tex
+++ b/graph/graph.tex
@@ -15,7 +15,7 @@
 	\end{itemize}
 \end{algorithm}
 
-\begin{algorithm}{Lowest Common Ancestor}
+\begin{algorithm}[optional]{Lowest Common Ancestor}
 	\begin{methods}
 		\method{init}{baut DFS-Baum über $g$ auf}{\abs{V}\*\log(\abs{V})}
 		\method{getLCA}{findet LCA}{1}
@@ -24,6 +24,16 @@
 	\sourcecode{graph/LCA_sparse.cpp}
 \end{algorithm}
 
+\begin{algorithm}{Binary Lifting}
+	\begin{methods}
+		\method{Lift}{constructor}{\abs{V}}
+		\method{depth}{distance to root of vertex $v$}{1}
+		\method{lift}{vertex above $v$ at depth $d$}{\log(\abs{V})}
+		\method{lca}{lowest common ancestor of $u$ and $v$}{\log(\abs{V})}
+	\end{methods}
+	\sourcecode{graph/binary_lifting.cpp}
+\end{algorithm}
+
 \begin{algorithm}{Centroids}
 	\begin{methods}
 		\method{find\_centroid}{findet alle Centroids des Baums (maximal 2)}{\abs{V}}
-- 
cgit v1.2.3

