# HG changeset patch
# User Markus Kaiser <markus.kaiser@in.tum.de>
# Date 1404578118 -7200
# Node ID faff67582175dc3303c3ce4eb64c295de448d426
# Parent  1d9a7448a28405acb51c9005c06d469f58392c9e
add bibliography; append preamble

diff -r 1d9a7448a284 -r faff67582175 minimum_bisection/paper/preamble.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/minimum_bisection/paper/preamble.tex	Sat Jul 05 18:35:18 2014 +0200
@@ -0,0 +1,37 @@
+\documentclass{llncs}
+
+\usepackage[english]{babel}
+
+\usepackage[T1]{fontenc}
+\usepackage[utf8]{inputenc}
+
+% \usepackage{xcolor}
+% \usepackage{tabu}
+\usepackage{tikz}
+\usepackage{pgfplots}
+\pgfplotsset{compat=1.9}
+\usetikzlibrary{shapes}
+\usetikzlibrary{fit}
+
+\usepackage{amsmath}
+\usepackage{mathdots}
+\usepackage{mathtools}
+\mathtoolsset{showonlyrefs,showmanualtags}
+\usepackage{mathrsfs}
+\usepackage{csquotes}
+
+\usepackage[pdftex]{hyperref}
+
+\newcommand{\R}{\mathbb{R}}
+\newcommand{\Oh}{\mathcal{O}}
+\newcommand{\Ih}{\mathcal{I}}
+\newcommand{\Ell}{\mathcal{L}}
+
+\newcommand{\abs}[1]{\left\vert #1 \right\vert}
+\newcommand{\powerset}[1]{\mathcal{P}\left( #1 \right)}
+\newcommand{\setnot}[1]{\overline{#1}}
+\newcommand{\setsymdiff}{\,\triangle\,}
+
+\newcommand{\defeq}{\coloneqq} %Mathtools already defines this
+
+\DeclareMathOperator{\st}{s.t.}
diff -r 1d9a7448a284 -r faff67582175 minimum_bisection/paper/term_paper.bib
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/minimum_bisection/paper/term_paper.bib	Sat Jul 05 18:35:18 2014 +0200
@@ -0,0 +1,34 @@
+@inproceedings{azar2003optimal,
+  title={Optimal oblivious routing in polynomial time},
+  author={Azar, Yossi and Cohen, Edith and Fiat, Amos and Kaplan, Haim and R{\"a}cke, Harald},
+  booktitle={Proceedings of the thirty-fifth annual ACM symposium on Theory of computing},
+  pages={383--388},
+  year={2003},
+  organization={ACM}
+}
+
+@inproceedings{bienkowski2003practical,
+  title={A practical algorithm for constructing oblivious routing schemes},
+  author={Bienkowski, Marcin and Korzeniowski, Miroslaw and R{\"a}cke, Harald},
+  booktitle={Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures},
+  pages={24--33},
+  year={2003},
+  organization={ACM}
+}
+
+@inproceedings{racke2008optimal,
+  title={Optimal hierarchical decompositions for congestion minimization in networks},
+  author={R{\"a}cke, Harald},
+  booktitle={Proceedings of the fortieth annual ACM symposium on Theory of computing},
+  pages={255--264},
+  year={2008},
+  organization={ACM}
+}
+
+@book{approx,
+  title={The design of approximation algorithms},
+  author={Williamson, David P and Shmoys, David B},
+  year={2011},
+  publisher={Cambridge University Press},
+  pages={376--385}
+}
diff -r 1d9a7448a284 -r faff67582175 minimum_bisection/paper/term_paper.tex
--- a/minimum_bisection/paper/term_paper.tex	Sat Jul 05 17:28:05 2014 +0200
+++ b/minimum_bisection/paper/term_paper.tex	Sat Jul 05 18:35:18 2014 +0200
@@ -1,23 +1,10 @@
-\documentclass{llncs}
-
-\usepackage[german]{babel}
-\usepackage[T1]{fontenc}
-\usepackage[latin1]{inputenc}
-\usepackage{amsmath}
-\usepackage[pdftex]{hyperref}
+\input{preamble.tex}
+\input{tikzpictures.tex}
 
-\ifpdf
-    \usepackage[pdftex]{graphicx}
-    \DeclareGraphicsExtensions{.pdf, .png, .jpg}
-\else
-    \usepackage[dvips]{graphicx}
-    \DeclareGraphicsExtensions{.eps}
-\fi
-
-\title{Hier den Titel eintragen}
-\author{Hier den Namen eintragen}
+\title{Oblivious Routing and Minimum Bisection}
+\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
 \institute{Technische Universit\"at M\"unchen\\
-\email{example@in.tum.de}}
+\email{markus.kaiser@in.tum.de}}
 
 \begin{document}
 
@@ -29,7 +16,8 @@
 
 ...
 
+\nocite{*}
 \bibliographystyle{alpha}
-\bibliography{seminararbeit}
+\bibliography{term_paper}
 
 \end{document}
diff -r 1d9a7448a284 -r faff67582175 minimum_bisection/paper/tikzpictures.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/minimum_bisection/paper/tikzpictures.tex	Sat Jul 05 18:35:18 2014 +0200
@@ -0,0 +1,101 @@
+\pgfdeclarelayer{background}
+\pgfdeclarelayer{demand}
+\pgfdeclarelayer{marked}
+\pgfdeclarelayer{foreground}
+\pgfsetlayers{background,demand,marked,main,foreground}
+
+\tikzstyle{edge} = [thick]
+\tikzstyle{marked edge} = [edge, line width=3pt, tumorange]
+\tikzstyle{directed} = [arrows={-latex}, shorten >=1pt]
+\tikzstyle{node on edge} = [fill=white, circle, inner sep=1pt, font=\footnotesize]
+
+\tikzstyle{flow graph} = [x=4em, y=4.5em]
+\tikzstyle{flow node} = [circle, draw, thick, fill=tumblue!20, minimum size=6pt, inner sep=0pt]
+\tikzstyle{flow edge} = [edge]
+\tikzstyle{demand edge} = [edge, line width=2.5pt, arrows={-latex}, dotted, tumred!50]
+\tikzstyle{tree edge} = [marked edge, tumgreen]
+\tikzstyle{flow capacity} = [node on edge]
+\tikzstyle{flow demand} = [node on edge, text=tumred]
+
+\tikzstyle{highlight} = [draw=tumorange, very thick, rounded corners]
+
+\newcommand{\tikzmark}[1]{\tikz[overlay,remember picture,baseline] \node [anchor=base] (#1) {};}
+
+\newcommand{\flownodes}{%
+    \pgfmathsetseed{42}
+    \def\jiggliness{0.2}
+    \def\jiggle{++ (rand * \jiggliness, rand * \jiggliness)}
+
+    \path[use as bounding box] (-4, 2.7) rectangle (3.5,6.15);
+
+    \foreach \pos/\name in {
+        % {(0,1)/a},
+        {(-0.5,2.75)/b},
+        {(0.5,3.25)/c},
+        {(0.75,4)/d},
+        {(-0.5,4.5)/e},
+        {(-1.25,3.75)/f},
+        {(1.5,4.75)/g},
+        {(0,5.5)/h},
+        {(2.5,5.5)/i},
+        {(3.5,3.5)/j},
+        {(2.25,4)/k},
+        {(-2,6)/l},
+        {(-2.5,5)/m},
+        {(-4,5)/n}}
+    \draw \pos\jiggle node[flow node] (\name) {};
+    % \draw \pos\jiggle node[flow node, label={\name}, font=\footnotesize] (\name) {};
+}
+\newcommand{\flowedges}[1][]{%
+    \foreach \source/\dest in {
+        % {a/b}, {a/n}, {a/j},
+        {n/b}, {b/j}, {f/b}, {c/b},
+        {c/d}, {e/d}, {e/f}, {g/i},
+        {h/e}, {h/i}, {i/j}, {k/j},
+        {l/h}, {l/m}, {n/m},
+        {c/k}, {k/i}, {g/d}, {m/e}, {n/l},
+        {m/f}, {f/c}, {d/k}, {e/g}, {c/e}}
+    \draw[flow edge, #1] (\source) -- (\dest);
+}
+\newcommand{\flowcapacities}[1][]{%
+    \foreach \source/\dest/\capacity in {
+        % {a/b}, {a/n}, {a/j},
+        {n/b/2}, {b/j/10}, {c/b/3}, {f/b/4},
+        {c/d/4}, {e/d/2}, {e/f/4}, {g/i/2},
+        {h/e/1}, {h/i/2}, {i/j/6}, {k/j/4},
+        {l/h/3}, {l/m/4}, {n/m/5},
+        {c/k/4}, {k/i/3}, {g/d/1}, {m/e/4}, {n/l/6},
+        {m/f/1}, {f/c/2}, {d/k/4}, {e/g/1}, {c/e/5}}
+    \path (\source) -- node[flow capacity, #1]{\capacity} (\dest);
+}
+\newcommand{\flowdemands}{%
+    \begin{pgfonlayer}{demand}
+        \foreach \source/\dest/\demand/\pos/\bendage in {
+            {n/j/10/0.2/right},
+            {h/j/8/0.2/left},
+            {e/g/1/0.7/left},
+            {n/h/12/0.7/left},
+            {k/m/5/0.8/right}}
+        \draw[demand edge, bend \bendage=15] (\source) edge node[flow demand, pos=\pos]{\demand} (\dest);
+    \end{pgfonlayer}
+}
+\newcommand{\flowtreeedges}[1][]{%
+    \begin{pgfonlayer}{marked}
+        \foreach \source/ \dest in {
+            % {a/b},
+            {c/b},
+            {c/d}, {e/d}, {e/f}, {g/i},
+            {m/e}, {d/k}, {i/j}, {k/j},
+            {h/i}, {l/m}, {n/m}}
+        \draw [tree edge, #1] (\source.center) -- (\dest.center);
+    \end{pgfonlayer}
+}
+\newcommand{\flowtreeedgestwo}[1][]{%
+    \begin{pgfonlayer}{marked}
+        \foreach \source/ \dest in {
+            {n/l}, {l/h}, {h/i}, {i/g}, {i/j},
+            {j/k}, {g/d}, {d/c}, {g/e}, {c/f},
+            {f/m}, {f/b}}
+        \draw[tree edge, #1] (\source.center) -- (\dest.center);
+    \end{pgfonlayer}
+}