Name
Abstract | ||
|---|---|---|
A \emph{wheel} is a graph made of a cycle of length at least~4 together with a vertex that has at least three neighbors in the cycle. We prove that the problem whose instance is a graph $G$ and whose question is "does $G$ contains a wheel as an induced subgraph" is NP-complete. We also settle the complexity of several similar problems. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.2298/AADM131128023D | CoRR |
DocType | Volume | ISSN |
Journal | abs/1308.6433 | Applicable Analysis and Discrete Mathematics, 8:111-122, 2014 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Emilie Diot | 1 | 1 | 1.03 |
| Sébastien Tavenas | 2 | 14 | 5.19 |
| Nicolas Trotignon | 3 | 194 | 27.96 |