Talk:Covering (graph theory)

Cleanup

It'll be nice to fix the duplicated definitions and add a nice picture representing a minimal covering. Stdazi (talk) 20:58, 8 July 2008 (UTC)[reply]

Merger proposal

This page and Vertex cover problem duplicate most of their information, neither is really long enough to warrant a separate article. I propose to merge the algorithmic content from Vertex cover problem into this page, under a Algorithms and complexity headline. Thore Husfeldt (talk) 18:46, 11 December 2008 (UTC)[reply]

I support this proposal. Graph coloring is a good example of a page where algorithmic and non-algorithmic content happily coexist. — Miym (talk) 19:21, 11 December 2008 (UTC)[reply]

In fact, there are quite a few article “pairs” of the type Foo and Foo problem. Typically, the former contains little more than a definition, and the latter contains an overview of algorithmic results. Independent set and Independent set problem (that one even has a merger proposal active), Clique (graph theory) and Clique problem, this page, and probably many more. Neither really contains enough material (or even enough potential) to ever become a great article on its own. What would be the right place to suggest merging all pages of this kind? Thore Husfeldt (talk) 20:25, 12 December 2008 (UTC)[reply]

Another such pair is Hamiltonian path and Hamiltonian path problem. There was also a pair for Domatic partition, but I merged them. — Miym (talk) 23:25, 12 December 2008 (UTC)[reply]

... ~~and Domatic number itself should find its final home at Dominating set, which maybe really should be called Domination (graph theory) or Graph domination.~~ (changed my mind about this) Thore Husfeldt (talk) 08:29, 13 December 2008 (UTC)[reply]

I am not quite sure about your latest suggestion. The case of Domatic partition (domatic number) and Dominating set is analogous to the case of Vertex coloring (chromatic number) and Independent set. And I would definitely not suggest that both Vertex coloring and Independent set were merged into one page called Independence (graph theory). (Ok, the case is not 100% identical, as the words domatic and dominating resemble each other. But on the other hand, if we try to explain both dominating number and domatic number on one page, with illustrations of both concepts, the reader is likely to mix up these similar-sounding words.) Perhaps we can first try to merge some easier cases and discuss domatic partition later again (once we see, for example, what the merged version of Dominating set looks like). — Miym (talk) 10:19, 13 December 2008 (UTC)[reply]

Split proposal

At the risk of sounding silly: Now I implemented the page merge I proposed originally, let me immediately propose a split of this page into Vertex cover and Edge cover. I’ve looked through all of the incoming links, and virtually no referring pages are interested in Covering as a general concept — they all either talk about Vertex cover, or about Edge cover (mostly about the former). There seems to be no demand for an article about the unifying concept of something-cover. Another argument to favour such a split is that there are very few lines of the present article devoted to the “common“ concept — most of the article discusses either vertices or edges exclusively. A third argument might be constructed from “Appeal to most common external naming tradition,” – my feeling is that “Agnostic”-covering is not the most common way of presenting this material, but I haven’t done the legwork for that argument and may be wrong or biased. (The current page may continue in the form of a very short definition/disambiguation page that links to Vertex cover and Edge cover.) Thore Husfeldt (talk) 12:48, 22 February 2009 (UTC)[reply]

Please go ahead and split. I was going to suggest it, too. Then it would be easier to discuss algorithms for edge covering more thoroughly. (But let's keep the two pages interlinked, and remind the reader that even though there is superficial similarity in the problems, they are very different from the algorithmic perspective.) — Miym (talk) 15:24, 22 February 2009 (UTC)[reply]

Oh, one more thing. I would suggest that we create two new pages, Vertex cover and Edge cover. Then Covering (graph theory) could be just a disambiguation page with links to Vertex cover, Edge cover, Covering graph, etc. — Miym (talk) 15:29, 22 February 2009 (UTC)[reply]

Deletions

Two things seem to have been removed in the merge: a see-also link to covering graph, and the point that a minimum edge cover can be found in polynomial time. Wouldn't it be good to mention these? — Miym (talk) 15:13, 21 February 2009 (UTC)[reply]