Rubao Ji

"Dynamic Connectivity Algorithms for Feynman Diagrams"

Abstract:

A Feynman diagram of order n can be viewed as a matching on 2n nodes (edges in the matching are undirected and called V-lines) along with a permutation of the 2n nodes (represented by directed edges called G-lines). Dynamic connectivity algorithms for Feynman diagrams are described in this thesis. The algorithms have two major components: diagram update and connectivity query. Two approaches are used to maintain and update Feynman diagrams. The key data structure for the first approach is a splay forest, which has an amortized expected cost of O(log n). The second approach applies a treap forest, which has an expected cost of O(log n). For query operations, three algorithms were designed and implemented having expected costs per operation of O(n), O(log^2 n) and O(log n), respectively.

Both splay forests and treap forests were implemented with arrays, allowing the nodes to be switched to be found in constant time. Five experiments were carried out with our implementations. The results showed good agreement with the time complexity analysis, validating the algorithm design and implementation.