The isomorphism problem for classes of graphs closed under contraction
The isomorphism problem for classes of graphs closed under contraction
复制标题
收缩封闭图类的同构问题
DOI：
10.1007/bf01098279
复制
发表时间：
1991
期刊：
影响因子：
--
通讯作者：
I. Ponomarenko
中科院分区：
文献类型：
--
作者：
I. Ponomarenko
研究一类图的同构问题，其中任意图包含连通的诱导子图和由边的端点连续识别得到的图。主要的结果是建立了检验这类图是否同构的多项式时间算法存在的充分条件。证明了不满足这些条件的类是同构完备的。
We consider the isomorphism problem for graphs in classes which, together with any graph, contain its connected induced subgraphs and graphs obtained by successive identifications of endpoints of edges. The main result is to establish sufficient conditions for the existence of a polynomial time algorithm testing graphs of such classes for isomorphism. It is shown that classes failing to satisfy these conditions are isomorphism-complete.