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 <p>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.</p>
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
2.46 MB
Adobe Portable Document Format