![]() | This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||
|
The argumentation in the section on computational complexity is flawed since reducing a problem on to an NP-hard problem does not mean anything for the complexity of the original problem, in other words one can use an NP-hard problem to solve even very easy problems. The argumentation should be built the other way around, showing how to do a reduction of dominating set to k-center. Tomash ( talk) 14:57, 21 February 2013 (UTC)
Isn't this problem the same as the one presented in the article Vertex k-center problem? AmirOnWiki ( talk) 13:17, 9 September 2021 (UTC)
![]() | This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||
|
The argumentation in the section on computational complexity is flawed since reducing a problem on to an NP-hard problem does not mean anything for the complexity of the original problem, in other words one can use an NP-hard problem to solve even very easy problems. The argumentation should be built the other way around, showing how to do a reduction of dominating set to k-center. Tomash ( talk) 14:57, 21 February 2013 (UTC)
Isn't this problem the same as the one presented in the article Vertex k-center problem? AmirOnWiki ( talk) 13:17, 9 September 2021 (UTC)