Talk:Closure problem

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mining (Rated C-class, Low-importance)
WikiProject icon This article is within the scope of WikiProject Mining, a collaborative project to organize and improve articles related to mining and mineral industries. If you would like to participate, you can edit the attached article, or visit the project page, where you can see a list of open tasks, join in the discussion, or join the project.
C-Class article C  This article has been rated as C-Class on the project's quality scale.
 Low  This article has been rated as Low-importance on the project's importance scale.

where is the definition of s-t graph ? Juanpabloaj (talk) 15:19, 30 August 2011 (UTC)

Definition ambiguity[edit]

"a closure of a directed graph is a set of vertices with no outgoing edges"

This is highly ambiguous. Is the closure simply a subset of sinks with maximum weight? Or is it a subgraph? I assume the latter, the section on mining wouldn't make any sense. — Preceding unsigned comment added by (talk) 23:40, 5 November 2014 (UTC)

It's the latter. "Outgoing" means from the whole set, not just from a vertex within the set. —David Eppstein (talk) 00:02, 6 November 2014 (UTC)

Maximum-weight vs. minimum-weight closure[edit]

Regarding this sentence:

The maximum-weight closure of a given graph G is the same as the complement of the minimum-weight closure on the transpose graph of G

Isn't this equivalent to saying that a maximum-weight closure of a graph is a minimum-weight closure of the same graph with weights negated? Personally I think that is a more intuitive reduction. Or is there are good reason for using the current phrasing that I'm missing? SuprDewd (talk) 13:07, 6 October 2016 (UTC)

No, it's saying that it's a min-weight closure on a graph with the same weights but with the edges reversed. —David Eppstein (talk) 16:06, 6 October 2016 (UTC)
Yes, I got that. But I see now that my question was poorly worded. What I meant to ask was, would my proposed reduction be a better fit for this page because it's slightly simpler and a bit more intuitive? SuprDewd (talk) 23:30, 6 October 2016 (UTC)
Ok, I see. Yes, I think it's a little simpler. —David Eppstein (talk) 00:27, 7 October 2016 (UTC)

Error on the picture with the cut[edit]

Reduction from closure to maximum flow

Shown cut on the picture cannot not be minimal, because edges (s,6) or (s,7) are not saturated. With given weights the minimal cut separates vertex-t from all other vertices. Or numbers in vertices are not weights but only ids? — Preceding unsigned comment added by (talk) 16:46, 12 November 2017 (UTC)

The numbers might be negative, in which case it would be preferable not to saturate those edges. (In fact the closure problem is only non-trivial when some numbers have different signs from each other.) —David Eppstein (talk) 17:11, 12 November 2017 (UTC)