Efficient Enumeration of Substructures in Sparse Graphs
和宏 栗田 · Hokkaido University Collection of Scholarly and Academic Papers (Hokkaido University) · 2020
Graphs are widely used to represent various data.For example, communication networks, metabolic networks, and social networks are graphs in the real world.In this thesis, we address efficient enumeration for sparse graphs.The first parameter of sparsity is girth.Small cycles make a problem difficult not only an enumeration problem but also optimization problems.For example, the minimum dominating set, the maximum independent set, and the maximum induced matching problem have a fixed parameter tractability.Indeed, we develop efficient enumeration algorithms for dominating sets and induced matchings if an input graph has large girth.In addition, we address another approach that uses the sparsity for subgraph enumeration.We next consider the problem which the output has girth constraint.In addition to girth, the other parameters of sparsity are degeneracy and degree.We develop several theoretical efficient enumeration algorithms.To show that these algorithms are practical, we experiment these algorithms for artificial graph data.As a result, our algorithms are faster than simple algorithms.In what follows, we explain our main results.In Chapter 3, we use girth as the sparsity.More precisely, we assume that an input graph has no cycles with length four.We address an induced matching enumeration problem.An induced matching is a set of edges such that the distance between any pair of edges is at least two.We propose a binary partition based enumeration algorithm.Arimura.This thesis would not have been possible without his support and encouragement.I would also like to express thanks to associate professor Takuya Kida.He always helped me when I