|
Zapiski Nauchnykh Seminarov LOMI, 1988, Volume 174, Pages 147–177
(Mi znsl4516)
|
|
|
|
This article is cited in 31 scientific papers (total in 31 papers)
Isomorphism problem for classes of graphs closed under contractions
I. N. Ponomarenko
Abstract:
A graph $G$ is contracted to graph $H$ if $H$ can be obtained from an induced subgraph of $G$ by contracting edged. The main purpose of the paper is to describe $C$-classes, i.e. classes of graphs closed under the contractions, from the point of view isomorphism problem. The key part of the considerations is connected to constructing polynomial-time algorithm to test isomorphism of graphs with bounded Hadviger number. The algorithm involves combinatorial properties of graphs from above class and group-theoretical ones of their automorphism groups. The result about graphs with bounded Hadviger number gives opportunity to characterise both isomorphism-complete $C$-classes and $C$-classes with polynomial-time isomorphism test.
Citation:
I. N. Ponomarenko, “Isomorphism problem for classes of graphs closed under contractions”, Computational complexity theory. Part 3, Zap. Nauchn. Sem. LOMI, 174, "Nauka", Leningrad. Otdel., Leningrad, 1988, 147–177; J. Soviet Math., 55:2 (1991), 1621–1643
Linking options:
https://www.mathnet.ru/eng/znsl4516 https://www.mathnet.ru/eng/znsl/v174/p147
|
Statistics & downloads: |
Abstract page: | 242 | Full-text PDF : | 167 |
|