Timeline for complexity of dominating sets of regular graphs
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 10, 2013 at 15:59 | answer | added | Martin Manrique | timeline score: 3 | |
| Feb 10, 2013 at 15:55 | comment | added | Martin Manrique | Thank you very much, Andrew D. King. I also found that it is NP-complete even for planar 4-regular graphs. | |
| Feb 7, 2013 at 18:32 | comment | added | Andrew D. King | Dominating set is NP-complete, and even APX-complete, for cubic graphs. dx.doi.org/10.1016/S0304-3975(98)00158-3 | |
| Feb 7, 2013 at 16:29 | history | asked | Martin Manrique | CC BY-SA 3.0 |