Graph Decomposition Using Node Labels
Öjvind Johansson · 2001
Dynamic programming is a method in which the solution to a computational problem is found by combination of already obtained solutions to subproblems. This method can be applied to problems on graphs (nodes connected by edges). The graph of interest must then be broken down into successively smaller parts according to some suitable principle. The thesis studies two graph algebras introduced for this purpose (Wanke 1994; Courcelle and Olariu 1994). Nodes have labels, and roughly, the operations are union, edge drawing, and relabeling. Once two nodes have acquired the same label, they can no longer be differentiated at subsequent edge drawings and relabelings. NLC-