The Library
Hamiltonian cycles in subcubic graphs : what makes the problem difficult
Tools
Tools
Tools
Korpelainen, Nicholas, Lozin, Vadim V. and Tiskin, Alexander (2010) Hamiltonian cycles in subcubic graphs : what makes the problem difficult. In: Kratochvil, J and Li, A and Fiala, J and Kolman, P, (eds.) Theory and Applications of Models of Computation. Lecture Notes in Computer Science, Vol.6108 . Springer, pp. 320-327. ISBN 9783642135613
![[img]](http://wrap.warwick.ac.uk/style/images/fileicons/application_pdf.png) |
PDF
fulltext7.pdf - Published Version Restricted to Repository staff only - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader Download (146Kb) |
Official URL: http://dx.doi.org/10.1007/978-3-642-13562-0_29
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: | Book Item |
|---|---|
| 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: | 9783642135613 |
| ISSN: | 0302-9743 |
| Book Title: | Theory and Applications of Models of Computation |
| 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 |
| Funder: | Engineering and Physical Sciences Research Council (EPSRC), DIMAP |
| 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
Actions (login required)
 |
View Item |
