## Efficient processing of hierarchical graphs

 dc.contributor.advisor David Fernadez-Baca dc.contributor.author Williams, Mark dc.contributor.department Computer Science dc.date 2018-08-17T14:15:39.000 dc.date.accessioned 2020-07-02T06:13:09Z dc.date.available 2020-07-02T06:13:09Z dc.date.copyright Mon Jan 01 00:00:00 UTC 1990 dc.date.issued 1990 dc.description.abstract

The standard representation of a graph is a list of its vertices and edges. However, graphs encountered in some areas have structural regularities that allow them to be represented using considerably less space. Typically, such a succinct encoding consists of a list of basic parts and a set of instructions for assembling the graph from the parts. Several models for succinctly representing graphs and other structures have been studied in the past. These models are capable of representing a graph using space polynomial in the logarithm of the size of the graph. Because of the potentially large difference in size between a graph and its description, it is natural to ask whether there are any problems that can be solved in time polynomial in the size of the succinct description, rather than in the size of the graph. It is known that even simple graph problems become NP-hard or worse under most models for succinct representation. Two exceptions are dynamic graphs and, the model we study, hierarchical graphs;A hierarchical graph [gamma] is a list of graphs and a set of rules describing how to attach the graphs together to form X([gamma]), the graph [gamma] represents. A hierarchical algorithm is an algorithm that, given [gamma], solves some problem defined on X([gamma]). Not every polynomially-solvable graph problem has a polynomial-time hierarchical algorithm. However, polynomial-time hierarchical algorithms for many problems have been developed using a framework called the bottom-up method;We develop a generalization of the bottom-up method that we use to construct and analyze hierarchical algorithms. Our method provides a uniform setting in which to present our algorithms, as well as many developed by other researchers. The problems we study belong to three classes: connectivity augmentation, subgraph homeomorphism, and matroid optimization. The P-connectivity augmentation problem, where P is a connectivity property, is to determine the number of edges that must be added to a graph to satisfy P. We present polynomial-time hierarchical algorithms for bridge-connectivity, biconnectivity, and strong-connectivity augmentation. Series-parallel and outer-planar graphs can be characterized by sets of forbidden graphs closed under homeomorphism. We present linear-time hierarchical algorithms that determine if X([gamma]) is series-parallel or outer-planar, and a polynomial-space hierarchical algorithm that generates a forbidden subgraph of X([gamma]) when one exists. The matroid optimization problem we consider is that of computing costs of optimum bases of matroids defined on graphs. We identify two infinite families of matroids for which polynomial-time hierarchical algorithms for this problem exist. We also develop polynomial-space hierarchical algorithms that generate optimum bases.

dc.format.mimetype application/pdf dc.identifier archive/lib.dr.iastate.edu/rtd/9385/ dc.identifier.articleid 10384 dc.identifier.contextkey 6359876 dc.identifier.doi https://doi.org/10.31274/rtd-180813-12666 dc.identifier.s3bucket isulib-bepress-aws-west dc.identifier.submissionpath rtd/9385 dc.identifier.uri https://dr.lib.iastate.edu/handle/20.500.12876/82478 dc.language.iso en dc.source.bitstream archive/lib.dr.iastate.edu/rtd/9385/r_9100452.pdf|||Sat Jan 15 02:32:10 UTC 2022 dc.subject.disciplines Computer Sciences dc.subject.keywords Computer science dc.title Efficient processing of hierarchical graphs dc.type article dc.type.genre dissertation dspace.entity.type Publication relation.isOrgUnitOfPublication f7be4eb9-d1d0-4081-859b-b15cee251456 thesis.degree.level dissertation thesis.degree.name Doctor of Philosophy
##### Original bundle
Now showing 1 - 1 of 1
Name:
r_9100452.pdf
Size:
2.46 MB
Format: