On the isomorphism problem for Helly circular-arc graphs

DOI10.1016/J.IC.2016.01.006zbMATH Open1336.05093arXiv1402.4642OpenAlexW1561090343MaRDI QIDQ259081FDOQ259081

Authors: Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky 

Publication date: 10 March 2016

Published in: Information and Computation (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1402.4642

Recommendations

• Helly circular-arc graph isomorphism is in logspace
• scientific article; zbMATH DE number 6829367
• Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs
• Linear-time recognition of Helly circular-arc models and graphs
• Around and beyond the isomorphism problem for interval graphs

zbMATH Keywords

circular-arc graphsgraph isomorphismgraph representationHelly propertylogarithmic space

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Topics in Intersection Graph Theory
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Efficient graph representations
• Linear-time recognition of circular-arc graphs
• Tractabilities and intractabilities on geometric intersection graphs
• Incidence matrices and interval graphs
• Helly circular-arc graph isomorphism is in logspace
• Solving the canonical representation and star system problems for proper circular-arc graphs in logspace
• Interval graphs: canonical representations in logspace
• Parallel recognition of the consecutive ones property with applications
• A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs
• Title not available (Why is that?)
• Algorithms on circular-arc graphs
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• On the Hardness of Graph Isomorphism
• $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Interval graph representation with given interval and intersection lengths
• Simple Geometrical Intersection Graphs
• Isomorphism of graph classes related to the circular-ones property
• Linear-time recognition of Helly circular-arc models and graphs
• Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs

Cited In (6)

• Around and beyond the isomorphism problem for interval graphs
• Hadwiger's conjecture for proper circular arc graphs
• Helly circular-arc graph isomorphism is in logspace
• Isomorphism of graph classes related to the circular-ones property
• Essential obstacles to Helly circular-arc graphs
• A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs

This page was built for publication: On the isomorphism problem for Helly circular-arc graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q259081)