LINEAR TIME ALGORITHM FOR DECIDING INTERVAL GRAPH ISOMORPHISM

被引：121
|
作者：
LUEKER, GS [1 ]
BOOTH, KS [1 ]
机构：
[1] UNIV WATERLOO, DEPT COMP SCI, WATERLOO N2L 3G1, ONTARIO, CANADA
来源：
JOURNAL OF THE ACM | 1979年 / 26卷 / 02期
关键词：
D O I：
10.1145/322123.322125
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
引用
收藏
页码：183 / 195
页数：13
相关论文
共 50 条
  • [1] A polynomial time algorithm for finding linear interval graph patterns
    Yamasaki, Hitoshi
    Shoudai, Takayoshi
    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, PROCEEDINGS, 2007, 4484 : 67 - +
  • [2] A LINEAR-TIME ALGORITHM FOR PROPER INTERVAL GRAPH RECOGNITION
    DEFIGUEIREDO, CMH
    MEIDANIS, J
    DEMELLO, CP
    INFORMATION PROCESSING LETTERS, 1995, 56 (03) : 179 - 184
  • [3] Circle Graph Isomorphism in Almost Linear Time
    Kalisz, Vit
    Klavik, Pavel
    Zeman, Peter
    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, TAMC 2022, 2022, 13571 : 176 - 188
  • [4] A Polynomial Time Algorithm for Undirected Graph Isomorphism
    Hou, Aimin
    Hao, Zhifeng
    WORLD CONGRESS ON ENGINEERING, WCE 2011, VOL II, 2011, : 1236 - 1239
  • [5] A SIMPLE LINEAR-TIME ALGORITHM FOR COMPUTING THE CENTER OF AN INTERVAL GRAPH
    OLARIU, S
    INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 1990, 34 (3-4) : 121 - 128
  • [6] A linear-time algorithm to compute a MAD tree of an interval graph
    Dahlhaus, E
    Dankelmann, P
    Ravi, R
    INFORMATION PROCESSING LETTERS, 2004, 89 (05) : 255 - 259
  • [7] LINEAR TIME ALGORITHM FOR DECIDING SUBJECT SECURITY
    LIPTON, RJ
    SNYDER, L
    JOURNAL OF THE ACM, 1977, 24 (03) : 455 - 464
  • [8] A Polynomial Time Algorithm for Finding a Minimally Generalized Linear Interval Graph Pattern
    Yamasaki, Hitoshi
    Shoudai, Takayoshi
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2009, E92D (02): : 120 - 129
  • [9] A polynomial time algorithm for finding a minimally generalized linear interval graph pattern
    Department of Informatics, Kyushu University, Fukuoka-shi, 819-0395, Japan
    IEICE Trans Inf Syst, 2 (120-129):
  • [10] Graph and Map Isomorphism and All Polyhedral Embeddings In Linear Time
    Kawarabayashi, Ken-ichi
    Mohar, Bojan
    STOC'08: PROCEEDINGS OF THE 2008 ACM INTERNATIONAL SYMPOSIUM ON THEORY OF COMPUTING, 2008, : 471 - +
12345