Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
Hamiltonian cycles in subcubic graphs: What makes the problem difficult. / Korpelainen, Nicholas; Lozin, Vadim V.; Tiskin, Alexander.
Theory and Applications of Models of Computation (TAMC 2010). 2010. стр. 320-327 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 6108).Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
}
TY - GEN
T1 - Hamiltonian cycles in subcubic graphs: What makes the problem difficult
AU - Korpelainen, Nicholas
AU - Lozin, Vadim V.
AU - Tiskin, Alexander
PY - 2010/7/15
Y1 - 2010/7/15
N2 - We study the computational complexity of the hamiltonian cycle problem in the class of graphs of vertex degree at most 3. Our goal is to distinguish boundary properties of graphs that make the problem difficult (NP-complete) in this domain. In the present paper, we discover the first boundary class of graphs for the hamiltonian cycle problem in subcubic graphs. © 2010 Springer-Verlag.
AB - We study the computational complexity of the hamiltonian cycle problem in the class of graphs of vertex degree at most 3. Our goal is to distinguish boundary properties of graphs that make the problem difficult (NP-complete) in this domain. In the present paper, we discover the first boundary class of graphs for the hamiltonian cycle problem in subcubic graphs. © 2010 Springer-Verlag.
UR - http://www.scopus.com/inward/record.url?scp=77954438425&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-13562-0_29
DO - 10.1007/978-3-642-13562-0_29
M3 - Conference contribution
AN - SCOPUS:77954438425
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 320
EP - 327
BT - Theory and Applications of Models of Computation (TAMC 2010)
ER -
ID: 127758076