License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2012.387
URN: urn:nbn:de:0030-drops-38757
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3875/
Go to the corresponding LIPIcs Volume Portal

Köbler, Johannes ; Kuhnert, Sebastian ; Verbitsky, Oleg

Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Logspace

pdf-format:
36.pdf (0.5 MB)

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 important class of hypergraphs corresponds to matrices with the circular ones property. Furthermore, we consider the Star System Problem that consists in reconstructing a graph from its closed neighborhood hypergraph. We show that this problem is solvable in logarithmic space for the classes of proper circular-arc, concave-round, and co-convex graphs.

BibTeX - Entry

@InProceedings{kbler_et_al:LIPIcs:2012:3875,
  author =	{Johannes K{\"o}bler and Sebastian Kuhnert and Oleg  Verbitsky},
  title =	{{Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Logspace}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) },
  pages =	{387--399},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-47-7},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{18},
  editor =	{Deepak D'Souza and Telikepalli Kavitha and Jaikumar Radhakrishnan},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2012/3875},
  URN =		{urn:nbn:de:0030-drops-38757},
  doi =		{10.4230/LIPIcs.FSTTCS.2012.387},
  annote =	{Keywords: Proper circular-arc graphs, graph isomorphism, canonization,   circular ones property, logspace complexity}
}

Keywords: Proper circular-arc graphs, graph isomorphism, canonization, circular ones property, logspace complexity
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)
Issue Date: 2012
Date of publication: 14.12.2012

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI