Name
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. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/978-3-642-13562-0_29 | TAMC |
Keywords | Field | DocType |
boundary property,vertex degree,subcubic graph,present paper,boundary class,hamiltonian cycle problem,hamiltonian cycle,computational complexity | Discrete mathematics,Indifference graph,Combinatorics,Computer science,Hamiltonian path,Chordal graph,Hamiltonian path problem,Vertex cover,Longest path problem,Computational complexity theory,Maximal independent set | Conference |
Volume | ISSN | ISBN |
6108 | 0302-9743 | 3-642-13561-7 |
Citations | PageRank | References |
1 | 0.37 | 8 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nicholas Korpelainen | 1 | 70 | 7.20 |
| Vadim V. Lozin | 2 | 947 | 83.65 |
| Alexander Tiskin | 3 | 220 | 15.50 |