Computer Science – Computational Complexity
Scientific paper
2012-02-20
Computer Science
Computational Complexity
44 pages, 8 figures, 2 tables; in this version, the Star System Problem is discussed in some more detail
Scientific paper
We present a logspace algorithm that constructs a canonical intersection model for a given proper circular-arc graph, where `canonical' means that models of isomorphic graphs are equal. This implies that the recognition and the isomorphism problems for this class of graphs are solvable in logspace. For a broader class of concave-round graphs, that still possess (not necessary proper) circular-arc models, we show that the latter can also be constructed canonically in logspace. Finally, we consider the search version of the Star System Problem that consists in reconstruction of a graph from its closed neighborhood hypergraph. We solve it in logspace for the classes of proper circular-arc, concave-round, and co-convex graphs.
Köbler Johannes
Kuhnert Sebastian
Verbitsky Oleg
No associations
LandOfFree
Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Log-Space does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Log-Space, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Log-Space will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-565619