Talk:Closure problem
where is the definition of s-t graph ? Juanpabloaj (talk) 15:19, 30 August 2011 (UTC)Reply
 | This article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
| |||||||||||
Untitled
where is the definition of s-t graph ? Juanpabloaj (talk) 15:19, 30 August 2011 (UTC)
Definition ambiguity
"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
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
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)
Content Disclaimer
Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.
- The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
- There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
- It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
- Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
- Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.