Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Log-Space
| Autor: | Köbler, Johannes, Kuhnert, Sebastian, Verbitsky, Oleg |
|---|---|
| Rok vydání: | 2012 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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 necessarily proper) circular-arc models, we show that those can also be constructed canonically in logspace. As a building block for these results, we show how to compute canonical models of circular-arc hypergraphs in logspace, which are also known as matrices with the circular-ones property. Finally, we consider the search version of the Star System Problem that consists in reconstructing 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. Comment: 19 pages, 3 figures, major revision |
| Databáze: | arXiv |
| Externí odkaz: |
|