Implementation and evaluation of algorithms for finding subgraph isomorphisms using color-coding
We will describe fixed parameter tractable algorithms for finding simple paths and cycles in a graph. Therefore we will look at algorithms using random orientations, but the main focus lies on the algorithms using the method color-coding. We also discuss the derandomization of the algorithmsseveral random graphs.
We will see that the color-coding methods are generally more suitable for finding paths or cycles than the easier methods using random orientations, except for finding k-paths in dense graphs G with |E(G)| < k|V(G)|.