首页    期刊浏览 2024年08月22日 星期四
登录注册

文章基本信息

  • 标题:Helly Circular-Arc Graph Isomorphism is in Logspace
  • 本地全文:下载
  • 作者:Johannes Köbler ; Sebastian Kuhnert ; Oleg Verbitsky
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2013
  • 卷号:2013
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We present logspace algorithms for the canonical labeling problem and the representation problem of Helly circular-arc (HCA) graphs. The first step is a reduction to canonical labeling and representation of interval intersection matrices. In a second step, the Delta trees employed in McConnell's linear time representation algorithm for interval matrices are adapted to the logspace setting and endowed with additional information to allow canonization. As a consequence, the isomorphism and recognition problems for HCA graphs turn out to be logspace complete.

  • 关键词:Canonization; Graph Isomorphism; helly circular arc graphs; logspace completeness
国家哲学社会科学文献中心版权所有