X-Git-Url: https://git.lyx.org/gitweb/?a=blobdiff_plain;f=lib%2Fexamples%2Fbeamerlyxexample1.lyx;h=922cee1048d4b2c31b9eb95db34ecd32d451f7c6;hb=2dc84b69d5a040e6343e21606f1c16a7c0957383;hp=cf5482769f4726fc2ec233caee5379a51e90ae23;hpb=86559aa3187e1645aeb1bae869f6ebd9ce626a32;p=lyx.git diff --git a/lib/examples/beamerlyxexample1.lyx b/lib/examples/beamerlyxexample1.lyx index cf5482769f..922cee1048 100644 --- a/lib/examples/beamerlyxexample1.lyx +++ b/lib/examples/beamerlyxexample1.lyx @@ -1,7 +1,9 @@ -#LyX 2.1 created this file. For more info see http://www.lyx.org/ -\lyxformat 452 +#LyX 2.3 created this file. For more info see http://www.lyx.org/ +\lyxformat 544 \begin_document \begin_header +\save_transient_properties true +\origin /systemlyxdir/examples/ \textclass beamer \begin_preamble \beamertemplateshadingbackground{red!5}{structure!5} @@ -155,16 +157,18 @@ \language_package default \inputencoding auto \fontencoding global -\font_roman times -\font_sans default -\font_typewriter default -\font_math auto +\font_roman "lmodern" "default" +\font_sans "lmss" "default" +\font_typewriter "lmtt" "default" +\font_math "auto" "auto" \font_default_family default \use_non_tex_fonts false \font_sc false \font_osf false -\font_sf_scale 100 -\font_tt_scale 100 +\font_sf_scale 100 100 +\font_tt_scale 100 100 +\use_microtype false +\use_dash_ligatures false \graphics default \default_output_format default \output_sync 0 @@ -174,16 +178,19 @@ \spacing single \use_hyperref false \papersize default -\use_geometry false +\use_geometry true \use_package amsmath 2 \use_package amssymb 2 -\use_package esint 0 +\use_package cancel 1 +\use_package esint 1 \use_package mathdots 1 -\use_package mathtools 0 +\use_package mathtools 1 \use_package mhchem 1 -\use_package undertilde 0 +\use_package stackrel 1 +\use_package stmaryrd 1 +\use_package undertilde 1 \cite_engine basic -\cite_engine_type numerical +\cite_engine_type default \biblio_style plain \use_bibtopic false \use_indices false @@ -191,6 +198,7 @@ \suppress_date false \justification true \use_refstyle 0 +\use_minted 0 \index Index \shortcut idx \color #008000 @@ -199,7 +207,10 @@ \tocdepth 2 \paragraph_separation indent \paragraph_indentation default -\quotes_language english +\is_math_indent 0 +\math_numbering_side default +\quotes_style english +\dynamic_quotes 0 \papercolumns 1 \papersides 1 \paperpagestyle default @@ -246,10 +257,20 @@ ICSI January 30th, 2004 \end_layout -\begin_layout BeginFrame +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Outline \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Standard \begin_inset CommandInset toc LatexCommand tableofcontents @@ -270,13 +291,10 @@ status collapsed \end_layout -\begin_layout EndFrame - -\end_layout - +\end_deeper \begin_layout Standard \begin_inset ERT -status collapsed +status open \begin_layout Plain Layout @@ -339,10 +357,20 @@ Introduction What are Tournaments? \end_layout -\begin_layout BeginFrame +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Tournaments Consist of Jousts Between Knights \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Columns \end_layout @@ -541,6 +569,7 @@ What is a Tournament? status open \begin_layout Plain Layout + 1- \end_layout @@ -554,6 +583,7 @@ A group of knights. status open \begin_layout Plain Layout + 2- \end_layout @@ -567,6 +597,7 @@ Every pair has a joust. status open \begin_layout Plain Layout + 3- \end_layout @@ -577,10 +608,28 @@ In every joust one knight wins. \end_deeper \end_deeper -\begin_layout BeginFrame +\end_deeper +\begin_layout Standard +\begin_inset Separator plain +\end_inset + + +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Tournaments are Complete Directed Graphs \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Columns \end_layout @@ -795,6 +844,7 @@ end{pgfpicture} status collapsed \begin_layout Plain Layout + 2- \end_layout @@ -826,20 +876,39 @@ any two different vertices. \end_deeper \end_deeper -\begin_layout BeginFrame -\begin_inset ERT +\end_deeper +\begin_layout Standard +\begin_inset Separator plain +\end_inset + + +\end_layout + +\begin_layout Frame +\begin_inset Argument 2 status collapsed \begin_layout Plain Layout -[<+>] ++ \end_layout \end_inset + +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Tournaments Arise Naturally in Different Situations \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout ExampleBlock \begin_inset Argument 2 status collapsed @@ -864,7 +933,10 @@ The comparison relation may be cyclic, however. \end_layout \end_deeper -\begin_layout Separator +\begin_layout Standard +\begin_inset Separator plain +\end_inset + \end_layout @@ -892,7 +964,10 @@ Reviewers decide for any two candidates whom they prefer. \end_layout \end_deeper -\begin_layout Separator +\begin_layout Standard +\begin_inset Separator plain +\end_inset + \end_layout @@ -930,15 +1005,26 @@ It chooses from any two words the one more likely to be in . \end_layout +\end_deeper \end_deeper \begin_layout Subsection What Does ``Finding Paths'' Mean? \end_layout -\begin_layout BeginFrame +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout ``Finding Paths'' is Ambiguous \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Block \begin_inset Argument 2 status open @@ -953,6 +1039,7 @@ status open status open \begin_layout Plain Layout + 1 \end_layout @@ -972,6 +1059,7 @@ status open status open \begin_layout Plain Layout + 2-3 \end_layout @@ -995,6 +1083,7 @@ status open status open \begin_layout Plain Layout + 4-5 \end_layout @@ -1014,6 +1103,7 @@ status open status open \begin_layout Plain Layout + 6-7 \end_layout @@ -1033,6 +1123,7 @@ status open status open \begin_layout Plain Layout + 8-9 \end_layout @@ -1056,6 +1147,7 @@ status open status open \begin_layout Plain Layout + 10- \end_layout @@ -1120,6 +1212,7 @@ target status open \begin_layout Plain Layout + only@-9| visible@8- \end_layout @@ -1160,6 +1253,7 @@ phantom{p} status open \begin_layout Plain Layout + only@10- \end_layout @@ -1198,19 +1292,12 @@ nointerlineskip \end_layout \begin_layout Overprint - -\end_layout - -\begin_deeper -\begin_layout Standard -\begin_inset ERT -status collapsed +\begin_inset Argument item:1 +status open \begin_layout Plain Layout - -\backslash -onslide<1,3,5,7,9,11-12> +1,3,5,7,9,11-12 \end_layout \end_inset @@ -1218,6 +1305,7 @@ onslide<1,3,5,7,9,11-12> \end_layout +\begin_deeper \begin_layout Columns \begin_inset Argument 1 status open @@ -1241,6 +1329,7 @@ status open status open \begin_layout Plain Layout + 1-2 \end_layout @@ -1644,6 +1733,7 @@ status open status open \begin_layout Plain Layout + 3- \end_layout @@ -1675,6 +1765,7 @@ column{5cm} status collapsed \begin_layout Plain Layout + only@3- \end_layout @@ -1905,15 +1996,14 @@ end{pgfpicture} \end_deeper \end_deeper -\begin_layout Standard -\begin_inset ERT -status collapsed +\end_deeper +\begin_layout Overprint +\begin_inset Argument item:1 +status open \begin_layout Plain Layout - -\backslash -onslide<2,4,6,8,10> +2,4,6,8,10 \end_layout \end_inset @@ -1921,6 +2011,7 @@ onslide<2,4,6,8,10> \end_layout +\begin_deeper \begin_layout Block \begin_inset Argument 2 status collapsed @@ -1936,20 +2027,11 @@ Variants of Path Finding Problems \begin_deeper \begin_layout Description -\begin_inset Argument 2 -status open - -\begin_layout Plain Layout -Approximation Problem: -\end_layout - -\end_inset - - \begin_inset Argument item:1 status open \begin_layout Plain Layout + 2- \end_layout @@ -1972,6 +2054,16 @@ Problem: Is there a path from \end_inset ? +\begin_inset Argument 2 +status open + +\begin_layout Plain Layout +Approximation Problem: +\end_layout + +\end_inset + + \end_layout \begin_layout Description @@ -1979,6 +2071,7 @@ Problem: Is there a path from status open \begin_layout Plain Layout + 4- \end_layout @@ -2008,6 +2101,7 @@ Problem: Construct a path from status open \begin_layout Plain Layout + 6- \end_layout @@ -2037,6 +2131,7 @@ Problem: Construct a shortest path from status open \begin_layout Plain Layout + 8- \end_layout @@ -2074,6 +2169,7 @@ Problem: Is the distance of status open \begin_layout Plain Layout + 10- \end_layout @@ -2102,6 +2198,7 @@ Problem: Construct a path from approximately their distance. \end_layout +\end_deeper \end_deeper \end_deeper \begin_layout Section @@ -2131,7 +2228,11 @@ pgfdeclareimage[height=2cm,mask=computer-mask,interpolate=true]{computer}{beamer \end_layout -\begin_layout BeginFrame +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout The Classes L and NL are Defined via \begin_inset Newline newline \end_inset @@ -2139,6 +2240,12 @@ The Classes L and NL are Defined via Logspace Turing Machines \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Standard \begin_inset ERT status collapsed @@ -2156,7 +2263,12 @@ begin{pgfpicture}{-0.5cm}{0cm}{8cm}{5cm} \backslash pgfputat{ \backslash -pgfxy(0,4)}{ +pgfxy(0,4)}{% +\end_layout + +\begin_layout Plain Layout + + \backslash tape{input tape (read only), $n$ symbols}{}{3401234*3143223=}} \end_layout @@ -2174,7 +2286,12 @@ uncover<2->{% \backslash pgfputat{ \backslash -pgfxy(0,0.5)}{ +pgfxy(0,0.5)}{% +\end_layout + +\begin_layout Plain Layout + + \backslash tape{}{output tape (write only)}{10690836937182}} \end_layout @@ -2197,7 +2314,12 @@ uncover<3->{% \backslash pgfputat{ \backslash -pgfxy(7,2)}{ +pgfxy(7,2)}{% +\end_layout + +\begin_layout Plain Layout + + \backslash shorttape{work tape (read/write), $O( \backslash @@ -2210,7 +2332,12 @@ log n)$ symbols}{}{42}} \backslash pgfputat{ \backslash -pgfxy(1.75,2.5)}{ +pgfxy(1.75,2.5)}{% +\end_layout + +\begin_layout Plain Layout + + \backslash pgfbox[center,center]{ \backslash @@ -2282,10 +2409,28 @@ end{pgfpicture} \end_layout -\begin_layout BeginFrame +\end_deeper +\begin_layout Standard +\begin_inset Separator plain +\end_inset + + +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Logspace Turing Machines Are Quite Powerful \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Block \begin_inset Argument 2 status collapsed @@ -2344,20 +2489,49 @@ satisfiability with two literals per clause. \end_layout \end_deeper -\begin_layout BeginFrame -\begin_inset ERT +\end_deeper +\begin_layout Standard +\begin_inset Separator plain +\end_inset + + +\end_layout + +\begin_layout Frame +\begin_inset Argument 1 status collapsed \begin_layout Plain Layout -<1>[label=hierarchy] +1 +\end_layout + +\end_inset + + +\begin_inset Argument 3 +status collapsed + +\begin_layout Plain Layout +label=hierarchy \end_layout \end_inset + +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout The Complexity Class Hierarchy \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Standard \begin_inset ERT status collapsed @@ -2741,7 +2915,19 @@ end{pgfpicture} \end_layout -\begin_layout BeginFrame +\end_deeper +\begin_layout Standard +\begin_inset Separator plain +\end_inset + + +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout The Circuit Complexity Classes AC \begin_inset Formula $^{0}$ \end_inset @@ -2761,6 +2947,12 @@ The Circuit Complexity Classes AC Limit the Circuit Depth \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Standard \begin_inset ERT status collapsed @@ -2969,6 +3161,7 @@ bounded fan-in . \end_layout +\end_deeper \end_deeper \end_deeper \begin_layout AgainFrame @@ -2976,6 +3169,7 @@ bounded fan-in status collapsed \begin_layout Plain Layout + 2 \end_layout @@ -2988,7 +3182,11 @@ hierarchy Standard Complexity Results on Finding Paths \end_layout -\begin_layout BeginFrame +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout All Variants of Finding Paths in Directed Graphs \begin_inset Newline newline \end_inset @@ -2996,6 +3194,12 @@ All Variants of Finding Paths in Directed Graphs Are Equally Difficult \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Fact \begin_inset Formula $\Lang{reach}$ \end_inset @@ -3053,12 +3257,14 @@ the approximation problem in logspace iff . \end_layout +\end_deeper \end_deeper \begin_layout AgainFrame \begin_inset Argument 1 status collapsed \begin_layout Plain Layout + 3 \end_layout @@ -3067,7 +3273,11 @@ status collapsed hierarchy \end_layout -\begin_layout BeginFrame +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Finding Paths in Forests and Directed Paths is Easy, \begin_inset Newline newline \end_inset @@ -3075,6 +3285,12 @@ Finding Paths in Forests and Directed Paths is Easy, But Not Trivial \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Fact \begin_inset Formula $\Lang{reach}_{\operatorname{forest}}$ \end_inset @@ -3090,7 +3306,10 @@ But Not Trivial -complete. \end_layout -\begin_layout Separator +\begin_layout Standard +\begin_inset Separator plain +\end_inset + \end_layout @@ -3109,11 +3328,13 @@ But Not Trivial -complete. \end_layout +\end_deeper \begin_layout AgainFrame \begin_inset Argument 1 status collapsed \begin_layout Plain Layout + 4 \end_layout @@ -3130,12 +3351,22 @@ Finding Paths in Tournaments Complexity of: Does a Path Exist? \end_layout -\begin_layout BeginFrame +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Definition of the Tournament Reachability Problem \end_layout -\begin_layout Definition -Let +\end_inset + + +\end_layout + +\begin_deeper +\begin_layout Definition +Let \color none \color red @@ -3183,10 +3414,28 @@ there exists a path from \end_layout \end_deeper -\begin_layout BeginFrame +\end_deeper +\begin_layout Standard +\begin_inset Separator plain +\end_inset + + +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout The Tournament Reachability Problem is Very Easy \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Theorem \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}\in\Class{AC}^{0}$ \end_inset @@ -3239,12 +3488,14 @@ easier . \end_layout +\end_deeper \end_deeper \begin_layout AgainFrame \begin_inset Argument 1 -status collapsed +status open \begin_layout Plain Layout + 5 \end_layout @@ -3257,7 +3508,11 @@ hierarchy Complexity of: Construct a Shortest Path \end_layout -\begin_layout BeginFrame +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Finding a Shortest Path Is as Difficult as \begin_inset Newline newline \end_inset @@ -3265,6 +3520,12 @@ Finding a Shortest Path Is as Difficult as the Distance Problem \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Definition Let \color none @@ -3318,10 +3579,28 @@ the distance of \end_layout \end_deeper -\begin_layout BeginFrame +\end_deeper +\begin_layout Standard +\begin_inset Separator plain +\end_inset + + +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout The Tournament Distance Problem is Hard \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Theorem \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$ \end_inset @@ -3382,7 +3661,19 @@ in logarithmic space, iff . \end_layout -\begin_layout BeginFrame +\end_deeper +\begin_layout Standard +\begin_inset Separator plain +\end_inset + + +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Proof That \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$ \end_inset @@ -3390,6 +3681,12 @@ Proof That is NL-complete \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Standard \begin_inset ERT status collapsed @@ -3469,6 +3766,7 @@ Reduce status open \begin_layout Plain Layout + alert@1 \end_layout @@ -3490,6 +3788,7 @@ Is input status open \begin_layout Plain Layout + 2-| alert@2-8 \end_layout @@ -3511,6 +3810,7 @@ Map status open \begin_layout Plain Layout + 9-| alert@9 \end_layout @@ -3528,7 +3828,10 @@ Query: \end_layout \end_deeper -\begin_layout Separator +\begin_layout Standard +\begin_inset Separator plain +\end_inset + \end_layout @@ -3547,6 +3850,7 @@ Correctness status open \begin_layout Plain Layout + 10- \end_layout @@ -3561,6 +3865,7 @@ status open status open \begin_layout Plain Layout + 10-| alert@10-11 \end_layout @@ -3594,6 +3899,7 @@ a length-3 path in status open \begin_layout Plain Layout + 12-| alert@12-13 \end_layout @@ -4678,12 +4984,14 @@ end{pgfpicture} \end_layout +\end_deeper \end_deeper \begin_layout AgainFrame \begin_inset Argument 1 -status collapsed +status open \begin_layout Plain Layout + 6 \end_layout @@ -4696,10 +5004,20 @@ hierarchy Complexity of: Approximating the Shortest Path \end_layout -\begin_layout BeginFrame +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Approximators Compute Paths that Are Nearly As Short As a Shortest Path \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Definition An \color none @@ -4758,7 +5076,19 @@ a path from \end_layout \end_deeper -\begin_layout BeginFrame +\end_deeper +\begin_layout Standard +\begin_inset Separator plain +\end_inset + + +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout There Exists a Logspace Approximation Scheme for \begin_inset Newline newline \end_inset @@ -4766,6 +5096,12 @@ There Exists a Logspace Approximation Scheme for the Tournament Shortest Path Problem \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Theorem There exists an approximation scheme for \begin_inset Formula $\Lang{tournament-shortest-path}$ @@ -4816,11 +5152,13 @@ beamergotobutton{More Details}} \end_layout +\end_deeper \begin_layout AgainFrame \begin_inset Argument 1 status collapsed \begin_layout Plain Layout + 7 \end_layout @@ -4829,10 +5167,6 @@ status collapsed hierarchy \end_layout -\begin_layout EndFrame - -\end_layout - \begin_layout Standard \begin_inset Note Note status open @@ -4847,14 +5181,8 @@ fragile \end_inset . - This is not yet supported by LyX, so the frame is created using TeX code. - Note that the -\backslash -begin{frame}[fragile] needs to be preceeded by an -\emph on -EndFrame -\emph default - environment. + \SpecialChar LyX + has the FragileFrame layout for this. \end_layout \end_inset @@ -4862,42 +5190,12 @@ EndFrame \end_layout -\begin_layout Standard -\begin_inset ERT +\begin_layout FragileFrame +\begin_inset Argument 4 status open \begin_layout Plain Layout - - -\backslash -begin{frame}[fragile] -\end_layout - -\end_inset - - -\end_layout - -\begin_layout Standard -\begin_inset ERT -status collapsed - -\begin_layout Plain Layout - - -\backslash -frametitle{ -\end_layout - -\end_inset - Just a frame with a program code listing -\begin_inset ERT -status collapsed - -\begin_layout Plain Layout - -} \end_layout \end_inset @@ -4905,10 +5203,11 @@ status collapsed \end_layout -\begin_layout Standard +\begin_layout FragileFrame This is some program code: \end_layout +\begin_deeper \begin_layout Standard \begin_inset listings lstparams "extendedchars=true,language=Python,numbers=left,stepnumber=3,tabsize=4" @@ -4965,22 +5264,7 @@ pass \end_layout -\begin_layout Standard -\begin_inset ERT -status open - -\begin_layout Plain Layout - - -\backslash -end{frame} -\end_layout - -\end_inset - - -\end_layout - +\end_deeper \begin_layout Section* Summary \end_layout @@ -4989,10 +5273,20 @@ Summary Summary \end_layout -\begin_layout BeginFrame +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Summary \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Block \begin_inset Argument 2 status collapsed @@ -5073,7 +5367,10 @@ in tournaments is \end_layout \end_deeper -\begin_layout Separator +\begin_layout Standard +\begin_inset Separator plain +\end_inset + \end_layout @@ -5145,15 +5442,26 @@ beamergotobutton{More Details}} \end_layout +\end_deeper \end_deeper \begin_layout Subsection* For Further Reading \end_layout -\begin_layout BeginFrame +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout For Further Reading \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Standard \begin_inset ERT status open @@ -5171,10 +5479,10 @@ beamertemplatebookbibitems \end_layout \begin_layout Bibliography -\labelwidthstring References \begin_inset CommandInset bibitem LatexCommand bibitem key "Moon1968" +literal "true" \end_inset @@ -5232,10 +5540,10 @@ beamertemplatearticlebibitems \end_layout \begin_layout Bibliography -\labelwidthstring References \begin_inset CommandInset bibitem LatexCommand bibitem key "NickelsenT2002" +literal "true" \end_inset @@ -5279,10 +5587,10 @@ Proc. \end_layout \begin_layout Bibliography -\labelwidthstring References \begin_inset CommandInset bibitem LatexCommand bibitem key "Tantau2004b" +literal "true" \end_inset @@ -5339,10 +5647,7 @@ newblock In press. \end_layout -\begin_layout EndFrame - -\end_layout - +\end_deeper \begin_layout Standard \start_of_appendix \begin_inset ERT @@ -5368,20 +5673,30 @@ Appendix Graphs With Bounded Independence Number \end_layout -\begin_layout BeginFrame -\begin_inset ERT +\begin_layout Frame +\begin_inset Argument 3 status collapsed \begin_layout Plain Layout - -[label=independence] +label=independence \end_layout \end_inset + +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Definition of Independence Number of a Graph \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Definition The \color none @@ -5411,7 +5726,19 @@ Tournaments have independence number 1. \end_layout -\begin_layout BeginFrame +\end_deeper +\begin_layout Standard +\begin_inset Separator plain +\end_inset + + +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout The Results for Tournaments also Apply to \begin_inset Newline newline \end_inset @@ -5419,6 +5746,12 @@ The Results for Tournaments also Apply to Graphs With Bounded Independence Number \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Theorem For each \begin_inset space ~ @@ -5455,7 +5788,10 @@ at most . \end_layout -\begin_layout Separator +\begin_layout Standard +\begin_inset Separator plain +\end_inset + \end_layout @@ -5488,7 +5824,10 @@ for approximating the shortest path in graphs with independence number at \end_layout -\begin_layout Separator +\begin_layout Standard +\begin_inset Separator plain +\end_inset + \end_layout @@ -5530,21 +5869,37 @@ in graphs with independence number at most . \end_layout +\end_deeper \begin_layout Subsection Finding Paths in Undirected Graphs \end_layout -\begin_layout BeginFrame -\begin_inset ERT +\begin_layout Frame +\begin_inset Argument 1 status collapsed \begin_layout Plain Layout -<1-2>[label=undirected] +1-2 +\end_layout + +\end_inset + + +\begin_inset Argument 3 +status collapsed + +\begin_layout Plain Layout +label=undirected \end_layout \end_inset + +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout The Complexity of Finding Paths in Undirected Graphs \begin_inset Newline newline \end_inset @@ -5552,6 +5907,12 @@ The Complexity of Finding Paths in Undirected Graphs Is Party Unknown. \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Fact \begin_inset Formula $\Lang{reach}_{\operatorname{undirected}}$ \end_inset @@ -5586,6 +5947,7 @@ status open status open \begin_layout Plain Layout + 1 \end_layout @@ -5632,6 +5994,7 @@ status open status open \begin_layout Plain Layout + 1 \end_layout @@ -5673,25 +6036,36 @@ the approximation problem in logspace iff ?. \end_layout +\end_deeper \end_deeper \begin_layout Subsection The Approximation Scheme is Optimal \end_layout -\begin_layout BeginFrame -\begin_inset ERT +\begin_layout Frame +\begin_inset Argument 3 status collapsed \begin_layout Plain Layout - -[label=optimality] +label=optimality \end_layout \end_inset + +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout The Approximation Scheme is Optimal \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Theorem Suppose there exists an approximation scheme for \begin_inset Formula $\Lang{tournament-shortest-path}$ @@ -5775,9 +6149,6 @@ qedhere \end_layout \end_deeper -\begin_layout EndFrame - -\end_layout - +\end_deeper \end_body \end_document