Springe direkt zu Inhalt

Pierre Lubitzsch:

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)|. 

Bachelor of Science (B.Sc.)