From 0c48c9bcad405fbf12de3eade2cef5d73a37d23a Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sun, 6 Apr 2008 18:00:50 +0200 Subject: [PATCH] Use larger parens. --- opt.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/opt.tex b/opt.tex index 52934ce..9a3a76f 100644 --- a/opt.tex +++ b/opt.tex @@ -1036,7 +1036,7 @@ have exactly~$t$ vertices. We define the computation so that it labels the graph its optimal decision tree. Then we apply Theorem \ref{topothm} combined with the brute-force construction of optimal decision trees from Lemma \ref{odtconst}. Together they guarantee that we can assign the decision trees to the subgraphs in time: -$$\O(\Vert\C\Vert + t^{t(2t+1)} \cdot (2^{2^{4t^2}} + t^2)) = \O(m).$$ +$$\O\Bigl(\Vert\C\Vert + t^{t(2t+1)} \cdot \bigl(2^{2^{4t^2}} + t^2\bigr)\Bigr) = \O(m).$$ Execution of the decision tree on each subgraph~$C_i$ then takes $\O(D(C_i))$ steps. The contracted graph~$G_A$ has at most $n/t = \O(n / \log^{(3)}n)$ vertices and asymptotically -- 2.39.2