Reductions
A reduction solves a problem $A$ with an algorithm for a problem $B$, which runs on an instance built from the input graph $G$. If the algorithm for $B$ takes $T$ rounds on that instance, the reduction solves $A$ in the number of rounds given below.
- $n', \Delta'$
- Number of nodes and maximum degree of the instance.
- $L(G)$
- Line graph: one node per edge of $G$, adjacent if the edges share an endpoint.
- $G \times K_{\Delta+1}$
- $\Delta+1$ copies of every node; the copies of a node form a clique, and the $i$-th copies of adjacent nodes are adjacent.
- $(C, D)$-ND
- Network decomposition: clusters of diameter at most $D$, colored with $C$ colors so that adjacent clusters get different colors.
- $c$
- Number of colors of a given coloring.
All reductions
Problem
| From | With runtime | To | Runtime | Instance | Models | Source | Technique |
|---|