Modular decomposition of undirected graphs
| dc.contributor.author | Esparza, Adrian E., author | |
| dc.contributor.author | McConnell, Ross, advisor | |
| dc.contributor.author | Pallickara, Sangmi, committee member | |
| dc.contributor.author | Hulpke, Alexander, committee member | |
| dc.date.accessioned | 2020-09-07T10:08:29Z | |
| dc.date.available | 2020-09-07T10:08:29Z | |
| dc.date.issued | 2020 | |
| dc.description.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. | |
| dc.format.medium | born digital | |
| dc.format.medium | masters theses | |
| dc.identifier | Esparza_colostate_0053N_16112.pdf | |
| dc.identifier.uri | https://hdl.handle.net/10217/212003 | |
| dc.language | English | |
| dc.language.iso | eng | |
| dc.publisher | Colorado State University. Libraries | |
| dc.relation.ispartof | 2020- | |
| dc.rights | Copyright and other restrictions may apply. User is responsible for compliance with all applicable laws. For information about copyright law, please see https://libguides.colostate.edu/copyright. | |
| dc.subject | modular decomposition | |
| dc.subject | graph theory | |
| dc.subject | modules | |
| dc.title | Modular decomposition of undirected graphs | |
| dc.type | Text | |
| dcterms.rights.dpla | This Item is protected by copyright and/or related rights (https://rightsstatements.org/vocab/InC/1.0/). You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s). | |
| thesis.degree.discipline | Computer Science | |
| thesis.degree.grantor | Colorado State University | |
| thesis.degree.level | Masters | |
| thesis.degree.name | Master of Science (M.S.) |
Files
Original bundle
1 - 1 of 1
Loading...
- Name:
- Esparza_colostate_0053N_16112.pdf
- Size:
- 614.95 KB
- Format:
- Adobe Portable Document Format