# Faster and Better Nested Dissection Orders for Customizable Contraction Hierarchies
## 3 Results
### Pareto Cut Experiments  
For the top-level cut experiments, we permute the nodes in preorder from a randomly selected start node, using the same start node for all partitioners. As discussed in Section 2.7, this is part of the recursive calls in the nested dissection implementation from [22]. We include it here to recreate the environment of a nested dissection on the top level. In Tables 4-7, we report the found cuts for various values of \(\varepsilon\) for all road networks. We use the partitioners KaHiP 2.11, IFC4, IFC8, IFC12, F3, F20, Metis, and Inertial Flow. We also report the actually achieved imbalance, the running time, and whether the sides of the cut are connected (\(\bullet\)) or not (\(\circ\)). We report \(\varepsilon=0.0\) only if perfect balance was achieved; otherwise, if the rounded value is 0.0, we report \(<0.1\%\). KaHIP was not able to achieve perfect balance for any of the graphs if perfect balance was desired. We note this by crossing out the respective values. This is due to our use of the KaHiP library interface that does not support enforcing balance. Metis simply rejects \(\varepsilon=0\), which is why we mark the corresponding entries with a dash. Perfect balance is not actually useful for the application. We solely include it to analyze the different Pareto cuts. Note that for FlowCutter and InertialFlowCutter, the running time always includes the computation of all more imbalanced cuts, i.e., to generate the full set of cuts, only the running time of the perfectly balanced cut is needed, while for all other partitioners, the sum of all reported running times is needed. Concerning the performance, Metis wins, but almost all reported cuts are larger than the cuts reported by FlowCutter, InertialFlowCutter, and KaHiP. Inertial Flow is also quite fast but, due to its design, produces cuts that are much more balanced than desired and thus can not achieve as small cuts as the other partitioners. \begin{table}
\begin{tabular}{c c c c c c c c c c c c c c c c c} \hline \hline \multirow{2}{*}{**\(\bullet\)**} & \multicolumn{8}{c}{**Achieved \(\varepsilon\) [\%]**} & \multicolumn{8}{c}{**Cut Size**} \\ \cline{2-13}  & **IFC4** & **IFC8** & **IFC12** & **F3** & **F20** & **K2.11** & **M** & **I** & **IFC4** & **IFC8** & **IFC12** & **F3** & **F20** & **K2.11** & **M** & **I** \\ \hline  
ullet\) & 0.1 & 0.2 & 0.3 & 0.6 & 3.0 & 27.7 & 0.1 & 0.2 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Pareto cuts of Colorado. \begin{table}
\begin{tabular}{c c c c c c c c c c c c c c c c c c c} \hline \hline \multirow{2}{*}{**Category**} & \multicolumn{10}{c}{**Achieved \(\varepsilon\) [\%]**} & \multicolumn{10}{c}{**Cut Size**} \\ \cline{2-13}  & **IFC4** & **IFC8** & **IFC12** & **F3** & **F20** & **K2.11** & **M** & **I** & **IFC4** & **IFC8** & **IFC12** & **F3** & **F20** & **K2.11** & **M** & **I** \\ \hline
0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & \(\downarrow\)0 & – & 0.0 & 311 & 289 & 288 & 273 & 271 & 148 & – & 1578 \\
1 & 1.0 & 1.0 & 0.3 & 0.7 & 0.3 & 1.0 & \(<\)0.1 & 0.3 & 274 & 274 & 243 & 246 & 224 & 148 & 393 & 417 \\
3 & 3.0 & 3.0 & 2.3 & 0.7 & 1.3 & 2.6 & \(<\)0.1 & 0.4 & 259 & 241 & 238 & 246 & 219 & 130 & 434 & 340 \\
5 & 4.8 & 4.8 & 4.2 & 4.6 & 5.0 & 2.9 & \(<\)0.1 & 0.2 & 226 & 226 & 215 & 211 & 207 & 129 & 452 & 299 \\
10 & 9.5 & 9.5 & 9.5 & 9.5 & 9.5 & 7.9 & \(<\)0.1 & 0.2 & 188 & 188 & 188 & 188 & 112 & 468 & 284 \\
20 & 9.5 & 9.5 & 9.5 & 9.5 & 9.5 & 7.8 & \(<\)0.1 & 7.5 & 188 & 188 & 188 & 188 & 113 & 403 & 229 \\
30 & 9.5 & 9.5 & 9.5 & 9.5 & 9.5 & 26.8 & \(<\)0.1 & 9.1 & 188 & 188 & 188 & 188 & 104 & 463 & 202 \\
50 & 49.0 & 49.0 & 49.0 & 9.5 & 43.7 & 8.2 & 33.3 & 9.5 & 23 & 23 & 23 & 188 & 39 & 111 & 16,151 & 188 \\
70 & 49.0 & 70.0 & 49.0 & 64.5 & 67.5 & 32.1 & 41.2 & 64.7 & 23 & 20 & 23 & 58 & 22 & 86 & 23,021 & 38 \\
90 & 72.8 & 72.8 & 72.8 & 72.8 & 72.8 & 72.8 & 72.8 & 72.8 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 \\ \hline \hline \end{tabular}
\end{table} 
Table 6: Pareto cuts of Europe.