Type the draft of the answer to question 2

1 files changed, 35 insertions, 1 deletions

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}