![]() | This ![]() It is of interest to the following WikiProjects: | ||||||||||||||||||||||||||||||
|
The reference to [1] contains an error in the algorithm as explained by mmiguel.martin. I added an alternative algroithm that suppose to do that but I didn't find any reference, I found the algorithm in a test solution of a course in the Open University of Israel. — Preceding unsigned comment added by 37.46.41.87 ( talk) 11:42, 4 June 2016 (UTC)
Should we merge everything from Vertex cover#Vertex cover in hypergraphs (and k-approximation of k-hitting set) to Set cover problem? The current situation is strange, as different aspects of the approximability of the set cover problem are discussed in different articles. — Miym ( talk) 22:41, 9 November 2009 (UTC)
The article claimed that vertex cover remains NP-complete
with a reference to Garey and Johnson (1977). I checked my copy and the claim is not supported there. According to page 190 it is the problem of connected vertex cover (where the set of vertices is required to be connected) that remains NP-complete for planar graphs. So I removed the claim. Gdr 10:42, 23 March 2012 (UTC)
In this section, the second of the two "vertex covers" seems to fail to meet the definition. Am I missing something? 73.32.71.188 ( talk) 14:40, 7 April 2021 (UTC)
Apparently, there are two different wikidata links, viz d:Q11515519 = vertex cover and d:Q924362 = vertex cover problem. I guess they should be merged, however, I don't know how to merge wikidata entries.
Moreover, the wikipedia link sets attached to the wikidata entries are not disjoint, their intersection is { de, it, ja, pl, ru }. In each of these languages, there exists one article about vertex cover, and another one about the vertex cover problem; in de and ru, one is a redirect to the other. So merging would require discussion in it, ja, pl - no idea how to find editors that are capable of these languages. - Jochen Burghardt ( talk) 20:57, 15 November 2023 (UTC)
![]() | This ![]() It is of interest to the following WikiProjects: | ||||||||||||||||||||||||||||||
|
The reference to [1] contains an error in the algorithm as explained by mmiguel.martin. I added an alternative algroithm that suppose to do that but I didn't find any reference, I found the algorithm in a test solution of a course in the Open University of Israel. — Preceding unsigned comment added by 37.46.41.87 ( talk) 11:42, 4 June 2016 (UTC)
Should we merge everything from Vertex cover#Vertex cover in hypergraphs (and k-approximation of k-hitting set) to Set cover problem? The current situation is strange, as different aspects of the approximability of the set cover problem are discussed in different articles. — Miym ( talk) 22:41, 9 November 2009 (UTC)
The article claimed that vertex cover remains NP-complete
with a reference to Garey and Johnson (1977). I checked my copy and the claim is not supported there. According to page 190 it is the problem of connected vertex cover (where the set of vertices is required to be connected) that remains NP-complete for planar graphs. So I removed the claim. Gdr 10:42, 23 March 2012 (UTC)
In this section, the second of the two "vertex covers" seems to fail to meet the definition. Am I missing something? 73.32.71.188 ( talk) 14:40, 7 April 2021 (UTC)
Apparently, there are two different wikidata links, viz d:Q11515519 = vertex cover and d:Q924362 = vertex cover problem. I guess they should be merged, however, I don't know how to merge wikidata entries.
Moreover, the wikipedia link sets attached to the wikidata entries are not disjoint, their intersection is { de, it, ja, pl, ru }. In each of these languages, there exists one article about vertex cover, and another one about the vertex cover problem; in de and ru, one is a redirect to the other. So merging would require discussion in it, ja, pl - no idea how to find editors that are capable of these languages. - Jochen Burghardt ( talk) 20:57, 15 November 2023 (UTC)