From fe90000730c6fc0d41f32e64a62c8c4209921856 Mon Sep 17 00:00:00 2001
From: Yigit Sever
Date: Sun, 15 Nov 2020 05:11:46 +0300
Subject: Type the draft of the answer to question 2

---
 main.tex | 36 +++++++++++++++++++++++++++++++++++-
 1 file changed, 35 insertions(+), 1 deletion(-)

(limited to 'main.tex')

diff --git a/main.tex b/main.tex
index da46b2a..ceb8e92 100644
--- a/main.tex
+++ b/main.tex
@@ -22,6 +22,8 @@
 \author{Yiğit Sever}
 \date{\today}
 
+\addbibresource{mylib.bib}
+
 %----------------------------------------------------------------------------------------
 
 \begin{document}
@@ -80,8 +82,40 @@ A modified graph traversal using either BFS or DFS (since a node can be discover
 
 With the assumption that accessing the labels $(u, w)$ takes $\mathcal{O}(1)$ time this algorithm has the same running time as BFS; $\mathcal{O}(m+n)$.
 
-
 \section{Reachability}%
 \label{sec:reachability}
 
+First, compute all strongly connected components (SCCs) of $G$ by using~\parencite{tarjanDepthFirst1972} per \emph{page 72} of the \nth{3} lecture notes in $\mathcal{O}(E+V)$ time. Instead of labelling the SCCs with the root node, we will initially label all nodes of the SCC $F'$ with the $min(u)$ of the connected component.
+
+Then, by ignoring the tree edges, shrink the graph $G$ such that $E' = {(v, w)~|~v \in F', w \in F''}$, leaving only cross links behind. This step takes another $\mathcal{O}(E+V)$ time.
+
+Now run the topological sort algorithm presented in \emph{page 84} of the \nth{3} lecture notes this operation is yet again $\mathcal{O}(E+V)$.
+
+Finally, reverse the direction of the edges on the graph that have been output by the topological sort and starting from the new root node, traverse the graph downwards and update the $min(u)$ of every SCC as follows;
+
+{\centering
+    \begin{minipage}{.7\linewidth}
+        \begin{algorithm}[H]
+            \DontPrintSemicolon{}
+            \SetAlgoLongEnd{}
+            \KwData{$G'$ = topological sorted G with reversed edges}
+            \KwResult{$\min(u)$ for all vertices $u \in V$}
+            $\text{mostmin} \longleftarrow \min(\text{root})$\;
+            \While{traversing $G'$ downwards with current node $v$}{
+                \uIf{$\min(v) < mostmin$}{
+                    $\text{mostmin} \longleftarrow \min(v)$\;
+                }
+                \Else{
+                    label $v$ as $mostmin$
+                }
+            }
+            \caption{Updating $\min(u)$ of the SCCs}%
+            \label{alg:question_2}
+        \end{algorithm}
+    \end{minipage}
+    \par
+}
+
+\printbibliography
+
 \end{document}
-- 
cgit v1.2.3-70-g09d2