%% This LaTeX-file was created by <jcl> Tue Feb 24 16:29:17 1998
%% LyX 0.12 (C) 1995-1998 by Matthias Ettrich and the LyX Team

%% Do not edit this file unless you know what you are doing.
\documentclass{article}
\usepackage[T1]{fontenc}

\makeatletter


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\newcommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\spacefactor1000}

\makeatother

\begin{document}


\section{Shur complement}

The Shur complement method is an asymptotically better way to calculate the
all points shortest path matrix.

\begin{enumerate}
\item Partition the graph into 2 sets of nodes \( \{S,T\} \)
\end{enumerate}
There will be 4 kinds of edges:

\( \begin{array}{ccc}
From/To & T & S\\
T & A & B\\
S & C & D
\end{array}=M \) As an example, \( B \) contains all edges from \( T \) to \( S \)

\begin{enumerate}
\item compute \( A^{*} \) (all internal connections in T)
\item \( F=D+CA^{*}B \)
\item \( F^{*} \)
\end{enumerate}
Form the matrix:

\( M^{*}=(\begin{array}{cc}
A^{*}+A^{*}BF^{*}CA^{*} & A^{*}BF^{*}\\
F^{*}CA^{*} & F^{*}
\end{array}) \)

This matrix is the all shortest path matrix.

Proof: Consider each possible path in terms of combinations of \( A,B,C,D \) and think about
which entries these will include.

\( (CA^{*}B)_{ij}= \) shortest path form i to j using only vertices in T.


\subsection{Timing analyses}

\( T(n)=2T(\frac{n}{2})+cn^{3}=cn^{3}+2c(\frac{n}{2})^{3}+...=O(n^{3}) \) This is better than the all points shortest path calculated by rings method.

\end{document}