Journal Article Graph Isomorphism Completeness for Trapezoid Graphs

高岡, 旭  ,  Takaoka, Asahi

E98-A ( No. 8 )  , pp.1838 - 1840 , 2015-08 , The Institute of Electronics, Information and Communication Engineers , 電子情報通信学会
Description
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.
Full-Text

http://t2r2.star.titech.ac.jp/rrws/file/CTT100695049/ATD100000413/Tak15-IEICE_GI.pdf

Number of accesses :  

Other information