# Faster and Better Nested Dissection Orders for Customizable Contraction Hierarchies
## 3 Results
### Order Experiments
#### 3.4.1 Quality  
Over all nodes \(v\), we report the average and maximum number of ancestors in the elimination tree, as well as the number of arcs incident to the ancestors. These metrics assess the search space sizes of an elimination tree query. The query times in Table 2 are correlated with search space size, as expected. The partitioner with the smallest average number of nodes and arcs in the search space always yields the fastest queries. Furthermore, we report the number of arcs in the CCH, i.e., shortcut and original arcs, the number of triangles, and an upper bound on the treewidth, which we obtained using the CCH order as an elimination ordering. A CCH is essentially a chordal supergraph of the input. Thus, CCHs are closely related to tree decompositions and elimination orderings. The relation between tree decompositions and Contraction Hierarchies is further explained in [35]. A low treewidth usually corresponds to good performance with respect to the other metrics. However, as the treewidth is defined by the largest bag in the tree decomposition which may depend on the size of few separators and disregards the size of all smaller separators, this is not always consistent. In the context of shortest path queries, a better average is preferable to a slightly reduced maximum. On the California and USA road networks, IFC12 yields the fastest queries and smallest average search space sizes, while on Europe IFC8 does. On Colorado, our smallest road network, F100 is slightly ahead of the InertialFlowCutter variants by 0.2 to 0.3 microseconds query time. IFC16 yields the fastest customization times for Colorado, Europe, and the USA, while IFC12 yields the fastest customization times for California. Customization times are correlated with the number of triangles. However, for Europe and the USA, the smallest number does not yield the fastest customizations. Even though we take the median of nine runs, this may still be due to random fluctuations. FlowCutter with at least 20 cutters has slightly worse average search space sizes and query times than InertialFlowCutter for California and the USA but falls behind for Europe. Thus, InertialFlowCutter computes the best CCH orders, with FlowCutter close behind. The different KaHiP variants and Inertial Flow compute the next best orders, while Metis is ranked last by a large margin. The ratio between maximum and average search space size is most strongly pronounced for Inertial Flow. This indicates that Inertial Flow works well for most separators, but the quality degrades for a few. InertialFlowCutter resolves this problem. \begin{table}
\begin{tabular}{c c c c c c c c c c c c} \hline \hline  & & \multicolumn{3}{c}{**Search Space**} & \multicolumn{2}{c}{**CCH**} & \multicolumn{3}{c}{**Up. **} & \multicolumn{3}{c}{**Running Times**} \\ \cline{3-11}  & & \multicolumn{2}{c}{**Nodes**} & \multicolumn{2}{c}{**Arcs [-10\({}^{3}\)]**} & \multicolumn{2}{c}{**Arcs [-10\({}^{6}\)]**} & \multicolumn{2}{c}{**\#Tri. **} & \multicolumn{2}{c}{**Tw. **} & \multicolumn{2}{c}{**Order**} & \multicolumn{2}{c}{**Cust. **} & \multicolumn{2}{c}{**Query**} \\ \cline{3-11}  & & **Avg. ** & **Max. ** & **Avg. ** & **Max. ** & **[-10\({}^{6}\)]** & **[-10\({}^{6}\)]** & **Bd. ** & **[s]** & **[ms]** & **[ms]** \\ \hline \multirow{11}{*}{\(\overline{\text{C}}\)} & M & 155.6 & 354 & 6.1 & 22.0 & 13.7 & 63.9 & 102 & 1.8 & 58.8 & 21.1 \\  & K0.61 & 135.1 & 357 & 4.6 & 21.6 & 16.7 & 72.4 & 103 & 3837  
There is an interesting difference in the number of cutters necessary for good CCH orders with InertialFlowCutter and FlowCutter. In [14], F20 is the recommended configuration. The performance differences between F20 and F100 are marginal (except for Europe). However, using just three cutters seems insufficient to get rid of bad random choices. For the InertialFlowCutter variants, four cutters suffice most of the time. The search space sizes, query times and customization times are very similar. This is also confirmed by the top-level cut experiments in Section 3.5.