Paper Info
Title
Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Logspace.
Abstract
We present a logspace algorithm that constructs a canonical intersection model for a given proper circular-arc graph, where canonical means that isomorphic graphs receive identical models. This implies that the recognition and the isomorphism problems for these graphs are solvable in logspace. For the broader class of concave-round graphs, which still possess (not necessarily proper) circular-arc models, we show that a canonical circular-arc model can also be constructed in logspace. As a building block for these results, we design a logspace algorithm for computing canonical circular-arc models of circular-arc hypergraphs. This class of hypergraphs corresponds to matrices with the circular ones property, which play an important role in computational genomics. Our results imply that there is a logspace algorithm that decides whether a given matrix has this property.
Year
DOI
Venue
2012
10.1016/j.jda.2016.03.001
Journal of Discrete Algorithms
Keywords
DocType
Volume
Graph isomorphism,Logspace,Circular-ones property,Intersection graphs
Journal
38
ISSN
Citations 
PageRank 
1570-8667
3
0.40
References 
Authors
18
3
Name
Order
Citations
PageRank
Johannes Köbler158046.51
Sebastian Kuhnert2366.52
Oleg Verbitsky319127.50