-#LyX 1.4.3 created this file. For more info see http://www.lyx.org/
-\lyxformat 245
+#LyX 1.5.0svn created this file. For more info see http://www.lyx.org/
+\lyxformat 276
\begin_document
\begin_header
\textclass beamer
\newcommand{\Lang}[1]{\operatorname{\text{\textsc{#1}}}}
+% This gets defined by beamerbasecolor.sty, but only at the beginning of
+% the document
+\colorlet{averagebackgroundcolor}{normal text.bg}
+
\newcommand{\tape}[3]{%
\color{structure!30!averagebackgroundcolor}
\pgfmoveto{\pgfxy(-0.5,0)}
\options notes=show
\language english
\inputencoding auto
-\fontscheme times
+\font_roman times
+\font_sans default
+\font_typewriter default
+\font_default_family default
+\font_sc false
+\font_osf false
+\font_sf_scale 100
+\font_tt_scale 100
\graphics default
\paperfontsize default
\spacing single
\papersize default
\use_geometry false
\use_amsmath 2
+\use_esint 0
\cite_engine basic
\use_bibtopic false
\paperorientation portrait
\papersides 1
\paperpagestyle default
\tracking_changes false
-\output_changes true
+\output_changes false
\end_header
\begin_body
\end_layout
\begin_layout Standard
-\begin_inset LatexCommand \tableofcontents{}
-
+\begin_inset LatexCommand tableofcontents
\end_inset
\end_inset
-A
+A
+\color none
+
\color red
tournament
-\color default
- is a
+\color none
+
+\color inherit
+is a
\end_layout
\begin_deeper
\begin_deeper
\begin_layout Itemize
-A
+A
+\color none
+
\color red
graph
-\color default
+\color none
+\color inherit
+
\begin_inset Formula $G=(V,E)$
\end_inset
-, a
+, a
+\color none
+
\color red
source
-\color default
+\color none
+\color inherit
+
\begin_inset Formula $s\in V$
\end_inset
- and a
+ and a
+\color none
+
\color red
target
-\color default
+\color none
+\color inherit
+
\begin_inset Formula $t\in V$
\end_inset
\end_inset
-A
+A
+\color none
+
\color red
maximum distance
-\color default
+\color inherit
\InsetSpace ~
\begin_inset Formula $d$
\end_inset
-An
+An
+\color none
+
\color red
approximation ratio
-\color default
+\color none
+\color inherit
+
\begin_inset Formula $r>1$
\end_inset
\end_layout
\begin_layout Definition
-Let
+Let
+\color none
+
\color red
\begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}$
\end_inset
-\color default
- contain all triples
+\color none
+
+\color inherit
+contain all triples
\begin_inset Formula $(T,s,t)$
\end_inset
\end_layout
\begin_layout Definition
-Let
+Let
+\color none
+
\color red
\begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
\end_inset
+
+\color none
-\color default
+\color inherit
contain all tuples
\begin_inset Formula $(T,s,t,d)$
\end_inset
\end_layout
\begin_layout Definition
-An
+An
+\color none
+
\color red
approximation scheme for
\begin_inset Formula $\Lang{tournament-shortest-path}$
\end_inset
-\color default
- gets as input
+\color none
+
+\color inherit
+gets as input
\end_layout
\begin_deeper
\begin_deeper
\begin_layout Itemize
-Tournament
+Tournament
+\color none
+
\color red
reachability
-\color default
- is in
-\color red
+\color none
+\color inherit
+is in
+\color none
+
+\color red
+
\begin_inset Formula $\Class{AC}^{0}$
\end_inset
-\color default
+\color inherit
.
\end_layout
\begin_layout Itemize
-There exists a
+There exists a
+\color none
+
\color red
logspace approximation scheme
-\color default
- for
+\color none
+
+\color inherit
+for
+\color none
+
\color red
approximating
-\color default
- shortest paths in tournaments.
+\color none
+
+\color inherit
+shortest paths in tournaments.
\end_layout
\begin_layout Itemize
-Finding
+Finding
+\color none
+
\color red
shortest paths
-\color default
- in tournaments is
-\color red
+\color none
+\color inherit
+in tournaments is
+\color none
+
+\color red
+
\begin_inset Formula $\Class{NL}$
\end_inset
-complete
-\color default
+\color inherit
.
\end_layout
\begin_layout Bibliography
-\bibitem {Moon1968}
+\begin_inset LatexCommand bibitem
+key "Moon1968"
+
+\end_inset
\InsetSpace ~
John Moon.
\end_inset
+
+\emph default
\emph on
Topics on Tournaments.
\begin_layout Bibliography
-\bibitem {NickelsenT2002}
+\begin_inset LatexCommand bibitem
+key "NickelsenT2002"
+
+\end_inset
\InsetSpace ~
Arfst Nickelsen and Till Tantau.
\end_inset
- In
+ In
+\emph default
+
\emph on
Proc.
of COCOON 2002
\begin_layout Bibliography
-\bibitem {Tantau2004b}
+\begin_inset LatexCommand bibitem
+key "Tantau2004b"
+
+\end_inset
\InsetSpace ~
Till Tantau
\begin_inset ERT
\end_inset
- In
+ In
+\emph default
+
\emph on
Proc.
of STACS 2004
\end_layout
\begin_layout Definition
-The
+The
+\color none
+
\color red
independence number
-\color default
+\color none
+\color inherit
+
\begin_inset Formula $\alpha(G)$
\end_inset
\begin_inset Formula $k$
\end_inset
-,
+,
+\color none
+
\color red
reachability
-\color default
- in graphs with independence number
+\color none
+
+\color inherit
+in graphs with independence number
\newline
at most\InsetSpace ~
\begin_inset Formula $k$
\end_inset
-, there exists a
+, there exists a
+\color none
+
\color red
logspace approximation scheme
-\color default
- for approximating the shortest path in graphs with independence number
+\color none
+
+\color inherit
+for approximating the shortest path in graphs with independence number
at most\InsetSpace ~
\begin_inset Formula $k$
\begin_inset Formula $k$
\end_inset
-, finding the
+, finding the
+\color none
+
\color red
shortest path
-\color default
- in graphs with independence number at most\InsetSpace ~
+\color none
+
+\color inherit
+in graphs with independence number at most\InsetSpace ~
\begin_inset Formula $k$
\end_inset
- is
+ is
+\color none
+
\color red
\begin_inset Formula $\Class{NL}$
\end_inset
-complete
-\color default
+\color inherit
.
\end_layout
projects / lyx.git / blobdiff