On the Isomorphism Problem for Helly Circular-Arc Graphs

Autor:	Köbler, Johannes, Kuhnert, Sebastian, Verbitsky, Oleg
Rok vydání:	2014
Předmět:	Computer Science - Computational Complexity Computer Science - Discrete Mathematics Mathematics - Combinatorics
Zdroj:	Information and Computation 247 (2016), pp. 266-277
Druh dokumentu:	Working Paper
DOI:	10.1016/j.ic.2016.01.006
Popis:	The isomorphism problem is known to be efficiently solvable for interval graphs, while for the larger class of circular-arc graphs its complexity status stays open. We consider the intermediate class of intersection graphs for families of circular arcs that satisfy the Helly property. We solve the isomorphism problem for this class in logarithmic space. If an input graph has a Helly circular-arc model, our algorithm constructs it canonically, which means that the models constructed for isomorphic graphs are equal. Comment: 22 pages, 5 figures. Section 5 is revised in this version
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1402.4642 Zobrazit plný text záznamu View this record from Arxiv