Korpelainen, Nicholas, Lozin, Vadim V. and Tiskin, Alexander (2010) Hamiltonian cycles in subcubic graphs : what makes the problem difficult. In: 7th International Conference on Theory and Application of Models of Computation, Prague, Czech Republic, June 07-11, 2010. Published in: Lecture Notes in Computer Science, Vol.6108 pp. 320-327.

Full text not available from this repository.

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.

Item Type:	Conference Item (Paper)
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Science > Computer Science Faculty of Science > Mathematics
Series Name:	Lecture Notes in Computer Science
Journal or Publication Title:	Lecture Notes in Computer Science
Publisher:	Springer
ISBN:	978-3-642-13561-3
ISSN:	0302-9743
Editor:	Kratochvil, J and Li, A and Fiala, J and Kolman, P
Date:	2010
Volume:	Vol.6108
Number of Pages:	8
Page Range:	pp. 320-327
Identification Number:	10.1007/978-3-642-13562-0_29
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Conference Paper Type:	Paper
Title of Event:	7th International Conference on Theory and Application of Models of Computation
Type of Event:	Conference
Location of Event:	Prague, Czech Republic
Date(s) of Event:	June 07-11, 2010
URI:	http://wrap.warwick.ac.uk/id/eprint/5581

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item