Timeline for Performing Transitive Reduction via neighbourhood and strongly connected components
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 9, 2014 at 8:58 | history | tweeted | twitter.com/#!/StackCompSci/status/509264451351371776 | ||
| Sep 4, 2014 at 18:17 | vote | accept | RAbraham | ||
| Sep 4, 2014 at 17:32 | answer | added | D.W.♦ | timeline score: 1 | |
| Sep 3, 2014 at 19:26 | comment | added | RAbraham | @D.W. I have edited the question with EDIT:EXAMPLE. Let me know if I can provide more information | |
| Sep 3, 2014 at 19:25 | history | edited | RAbraham | CC BY-SA 3.0 |
provided an example
|
| Sep 3, 2014 at 15:27 | comment | added | D.W.♦ | RAbraham, I still think you'll find it useful to try a few examples and see whether it works on them or not. See if you can construct a counterexample. That sometimes gives you enough insight that it all makes sense. If not, it might help you explain why you fear this might lose valid paths. After that the next thing would be to try to prove the correctness of this algorithm; you might tell us what proof outline you've tried and where you got stuck in completing the proof. | |
| Sep 3, 2014 at 12:05 | comment | added | RAbraham | @D.W.I think I have spent close to 12 hours on this problem before posting. I have tried working through examples on my own and I actually came up with a possible solution(which I had mentioned in the P.S) and I am not an university student, just the average programmer in awe of CS :). | |
| Sep 3, 2014 at 7:33 | comment | added | D.W.♦ | What have you done on your own to try to understand? Have you tried working through a few examples by hand? Have you tried to construct a counterexample, i.e., a graph where this algorithm gives an incorrect result (loses valid paths)? The best way to understand is probably to start by trying that on your own. | |
| Sep 2, 2014 at 16:03 | history | asked | RAbraham | CC BY-SA 3.0 |