| dc.creator |
Mujuni, Egbert |
|
| dc.date |
2016-09-21T13:23:29Z |
|
| dc.date |
2016-09-21T13:23:29Z |
|
| dc.date |
2008 |
|
| dc.date.accessioned |
2018-03-27T08:58:09Z |
|
| dc.date.available |
2018-03-27T08:58:09Z |
|
| dc.identifier |
Mujuni, E., 2008. Parameterized algorithms in smooth 4-regular Hamiltonian graphs. Mathematics in Computer Science, 1(4), pp.701-708. |
|
| dc.identifier |
1661-8289 |
|
| dc.identifier |
http://hdl.handle.net/20.500.11810/3930 |
|
| dc.identifier |
10.1007/s11786-007-0031-5 |
|
| dc.identifier.uri |
http://hdl.handle.net/20.500.11810/3930 |
|
| dc.description |
Full text can be accessed at
http://link.springer.com/article/10.1007/s11786-007-0031-5 |
|
| dc.description |
Smooth 4-regular hamiltonian graphs are generalizations of cycle plus triangles graphs. It has been shown that both the independent set and 3-colorability problems are NP-Complete in this class of graphs. In this paper we show that these problems are fixed parameter tractable if we choose the number of inner cycles as parameter. |
|
| dc.language |
en |
|
| dc.publisher |
Springer |
|
| dc.subject |
Algorithm |
|
| dc.subject |
Parameterized complexity |
|
| dc.subject |
Graph coloring |
|
| dc.subject |
Independent set |
|
| dc.title |
Parameterized Algorithms in Smooth 4-Regular Hamiltonian Graphs |
|
| dc.type |
Journal Article, Peer Reviewed |
|