Talk:Closure problem
 | This article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
| |||||||||||
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 209.221.240.193 (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)
- 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)
Error on the picture with the cut edit
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 87.255.2.2 (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)