Computational complexity aspects of implicit graph representations

Show simple item record

dc.identifier.uri Chandoo, Maurice ger 2018-08-08T15:21:02Z 2018-08-08T15:21:02Z 2018
dc.identifier.citation Chandoo, Maurice: Computational complexity aspects of implicit graph representations. Hannover : Gottfried Wilhelm Leibniz Universität, Diss., 2018, xiii, 89 S. DOI: ger
dc.description.abstract Implicit graph representations are immutable data structures for restricted classes of graphs such as planar graphs. A graph class has an implicit representation if the vertices of every graph in this class can be assigned short labels such that the adjacency of two vertices can be decided by an algorithm which gets the two labels of these vertices as input. A representation of a graph in that class is then given by the set of labels of its vertices. The algorithm which determines adjacency is only allowed to depend on the graph class. Such representations are attractive because they are space-efficient and in many cases also allow for constant-time edge queries. Therefore they outperform less specialized representations such as adjacency matrices or lists and are even optimal in an asymptotic sense. In the first part of this thesis we investigate the limitations of such representations when constraining the complexity of an algorithm which decodes adjacency. First, we prove that imposing such computational constraints does indeed affect what graph classes have an implicit representation. Then we observe that the adjacency structure of almost all graph classes that are known to have an implicit representation can be described by formulas of first-order logic. The quantifier-free fragment of this logic can be characterized in terms of RAMs: a graph class can be expressed by a quantifier-free formula if and only if it has an implicit representation where edges can be queried in constant-time on a RAM without division. We provide two reduction notions for graph classes which reveal that trees and interval graphs are representative for certain fragments of this logic. We conclude this part by providing a big picture of the newly introduced classes and point out viable research directions. In the second part we consider the tractability of algorithmic problems on graph classes with implicit representations. Intuitively, if a graph class has an implicit representation with very low complexity then it should have a simple adjacency structure. Therefore it seems plausible to expect certain algorithmic problems to be tractable on such graph classes. We consider how realistic it is to expect an algorithmic meta-theorem of the form ``if a graph class X has an implicit representation with complexity Y then problem Z is tractable on X''. Our considerations quickly reveal that even for the most humble choices of Y and various Z this is either impossible or leads to the frontiers of algorithmic research. We show that the complexity classes of graph classes introduced in the previous chapter can be interpreted as graph parameters and therefore can be considered within the framework of parameterized complexity. We embark on a case study where Z is the graph isomorphism problem and Y is the quantifier-free, four-variable fragment of first order logic with only the order predicate on the universe. This leads to a problem that has been studied independently and resisted classification for over two decades: the isomorphism problem for circular-arc (CA) graphs. We examine how a certain method, which we call flip trick, can be applied to this problem. We show that for a broad class of CA graphs the isomorphism problem reduces to the representation problem and as a consequence can be solved in polynomial-time. ger
dc.language.iso eng ger
dc.publisher Hannover : Institutionelles Repositorium der Leibniz Universität Hannover
dc.rights CC BY 3.0 DE ger
dc.rights.uri ger
dc.subject adjacency labeling schemes eng
dc.subject implicit graph conjecture eng
dc.subject circular-arc graph isomorphism eng
dc.subject Implizite Repräsentationen ger
dc.subject Kreisbogengraphen ger
dc.subject Graphenisomorphie ger
dc.subject.ddc 004 | Informatik ger
dc.title Computational complexity aspects of implicit graph representations ger
dc.type doctoralThesis ger
dc.type Text ger
dc.description.version publishedVersion ger
tib.accessRights frei zug�nglich ger

Files in this item

This item appears in the following Collection(s):

Show simple item record


Search the repository


My Account

Usage Statistics