Modular decomposition of undirected graphs
Date
2020
Authors
Esparza, Adrian E., author
McConnell, Ross, advisor
Pallickara, Sangmi, committee member
Hulpke, Alexander, committee member
Journal Title
Journal ISSN
Volume Title
Abstract
Graphs found in nature tend to have structure and interesting compositions that allow for compression of the information and thoughtful analysis of the relationships between vertices. Modular decomposition has been studied since 1967 [1]. Modular decomposition breaks a graph down into smaller components that, from the outside, are inseparable. In doing so, modules provide great potential to better study problems from genetics to compression. This paper describes the implementation of a practical algorithm to take a graph and decompose it into it modules in O(n+m log(n)) time. In the implementation of this algorithm, each sub-problem was solved using object oriented design principles to allow a reader to extract the individual objects and turn them to other problems of practical interest. The purpose of this paper is to provide the reader with the tools to easily compute: modular decomposition of an undirected graph, partition an undirected graph, depth first search on a directed partially complemented graph, and stack operations with a complement stack. The provided implementation of these problems all compute within the time bound discussed above, or even faster for several of the sub problems.
Description
Rights Access
Subject
modular decomposition
graph theory
modules