Graph Isomorphism Completeness for Trapezoid Graphs

被引：7
作者：
Takaoka, Asahi [1 ]
机构：
[1] Tokyo Inst Technol, Dept Commun & Comp Engn, Tokyo 1528550, Japan
来源：
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES | 2015年 / E98A卷 / 08期
关键词：
comparability graphs; graph isomorphism; interval dimension; trapezoid graphs; TOLERANCE GRAPHS; PERMUTATION GRAPHS; RECOGNITION; SETS;
D O I：
10.1587/transfun.E98.A.1838
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
The complexity of the graph isomorphism problem for trapezoid graphs has been open over a decade. This paper shows that the problem is GI-complete. More precisely, we show that the graph isomorphism problem is GI-complete for comparability graphs of partially ordered sets with interval dimension 2 and height 3. In contrast, the problem is known to be solvable in polynomial time for comparability graphs of partially ordered sets with interval dimension at most 2 and height at most 2.
引用
收藏
页码：1838 / 1840
页数：3
相关论文
共 19 条
[1]   PROPER AND UNIT TOLERANCE GRAPHS [J].
BOGART, KP ;
FISHBURN, PC ;
ISAAK, G ;
LANGLEY, L .
DISCRETE APPLIED MATHEMATICS, 1995, 60 (1-3) :99-117
[2]  
Booth K.S., 1979, CS7704 U WAT
[3]   ON TESTING ISOMORPHISM OF PERMUTATION GRAPHS [J].
COLBOURN, CJ .
NETWORKS, 1981, 11 (01) :13-21
[4]  
Corneil D. G., 1987, Congr. Numer., V58, P267
[5]  
Curtis AR, 2013, DISCRETE MATH THEOR, V15, P157
[6]   TRAPEZOID GRAPHS AND THEIR COLORING [J].
DAGAN, I ;
GOLUMBIC, MC ;
PINTER, RY .
DISCRETE APPLIED MATHEMATICS, 1988, 21 (01) :35-46
[7]   TOLERANCE GRAPHS [J].
GOLUMBIC, MC ;
MONMA, CL ;
TROTTER, WT .
DISCRETE APPLIED MATHEMATICS, 1984, 9 (02) :157-170
[8]   LINEAR TIME ALGORITHM FOR DECIDING INTERVAL GRAPH ISOMORPHISM [J].
LUEKER, GS ;
BOOTH, KS .
JOURNAL OF THE ACM, 1979, 26 (02) :183-195
[9]  
Mertzios GB, 2013, LECT NOTES COMPUT SC, V8125, P719, DOI 10.1007/978-3-642-40450-4_61
[10]   The recognition of triangle graphs [J].
Mertzios, George B. .
THEORETICAL COMPUTER SCIENCE, 2012, 438 :34-47
12