Standard

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).

Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › Рецензирование

Harvard

Korpelainen, N, Lozin, VV & Tiskin, A 2010, Hamiltonian cycles in subcubic graphs: What makes the problem difficult. в Theory and Applications of Models of Computation (TAMC 2010). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Том. 6108, стр. 320-327. https://doi.org/10.1007/978-3-642-13562-0_29

APA

Korpelainen, N., Lozin, V. V., & Tiskin, A. (2010). Hamiltonian cycles in subcubic graphs: What makes the problem difficult. в Theory and Applications of Models of Computation (TAMC 2010) (стр. 320-327). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 6108). https://doi.org/10.1007/978-3-642-13562-0_29

Vancouver

Korpelainen N, Lozin VV, Tiskin A. Hamiltonian cycles in subcubic graphs: What makes the problem difficult. в 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)). https://doi.org/10.1007/978-3-642-13562-0_29

Author

Korpelainen, Nicholas ; Lozin, Vadim V. ; Tiskin, Alexander. / Hamiltonian cycles in subcubic graphs: What makes the problem difficult. 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)).

BibTeX

@inproceedings{1c388d609edc42e8960509e2f8870f4c,
title = "Hamiltonian cycles in subcubic graphs: What makes the problem difficult",
abstract = "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. {\textcopyright} 2010 Springer-Verlag.",
author = "Nicholas Korpelainen and Lozin, {Vadim V.} and Alexander Tiskin",
year = "2010",
month = jul,
day = "15",
doi = "10.1007/978-3-642-13562-0_29",
language = "English",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "320--327",
booktitle = "Theory and Applications of Models of Computation (TAMC 2010)",

}

RIS

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