Transitive reduction: Revision history

Filter revisionsshowhide

To date:

Tag filter:

Invert selection

External tools:

For any version listed below, click on its date to view it. For more help, see Help:Page history and Help:Edit summary. (cur) = difference from current version, (prev) = difference from preceding version, m = minor edit, → = section edit, ← = automatic edit summary

curprev 13:3013:30, 19 September 2024‎ Citation bot talk contribs‎ 16,293 bytes +30‎ Altered issue. Added isbn. Formatted dashes. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Set theory | #UCB_Category 73/155 undo

curprev 13:2313:23, 28 May 2024‎ 141.76.29.166 talk‎ 16,263 bytes +20‎ fixed reference to topological order on dags undo Tag: Visual edit

curprev 19:3619:36, 13 February 2024‎ Joshuagmath talk contribs‎ 16,243 bytes +95‎ →‎Computational complexity: Added note explaining how you can apply matrix mult over complex numbers to transitive reduction undo

curprev 17:3717:37, 8 September 2023‎ Jochen Burghardt talk contribs‎ 12,428 bytes −33‎ →‎In directed acyclic graphs: resolve DAB link undo
curprev 09:1209:12, 8 September 2023‎ Onel5969 talk contribs‎ m 12,461 bytes +26‎ Disambiguating links to Transitivity (help needed) using DisamAssist. undo

curprev 18:0018:00, 12 August 2023‎ OAbot talk contribs‎ m 12,435 bytes +21‎ Open access bot: doi added to citation with #oabot. undo

curprev 16:3116:31, 20 April 2023‎ David Eppstein talk contribs‎ 12,414 bytes 0‎ Undid revision 1150886703 by David Eppstein (talk) nvm, misread diff, I prefer this word order undo Tag: Undo
curprev 16:2916:29, 20 April 2023‎ David Eppstein talk contribs‎ 12,414 bytes 0‎ Undid revision 1150874333 by Abe149 (talk) this discusses graphs that might not be acyclic undo Tags: Undo Reverted
curprev 15:1915:19, 20 April 2023‎ Abe149 talk contribs‎ m 12,414 bytes 0‎ →‎In acyclic directed graphs undo Tag: Reverted

curprev 12:1712:17, 2 March 2023‎ AnomieBOT talk contribs‎ m 12,414 bytes +16‎ Dating maintenance tags: {{Example needed}} undo
curprev 11:5611:56, 2 March 2023‎ Jochen Burghardt talk contribs‎ 12,398 bytes +135‎ →‎top: example needed undo

curprev 03:0203:02, 17 October 2022‎ Michael Hardy talk contribs‎ 12,263 bytes 0‎ No edit summary undo

curprev 12:0012:00, 1 September 2022‎ 181.169.109.9 talk‎ 12,263 bytes −17‎ Fixed two errors: removed "transitive reduction is a tree" (does not even hold in the article's shown example), changed "induced subgraph" to "spanning subgraph" undo

curprev 07:3007:30, 26 June 2022‎ OlliverWithDoubleL talk contribs‎ m 12,280 bytes −10‎ No edit summary undo Tags: Mobile edit Mobile app edit iOS app edit
curprev 07:2907:29, 26 June 2022‎ OlliverWithDoubleL talk contribs‎ 12,290 bytes +259‎ short description, math formatting, links undo Tags: Mobile edit Mobile app edit iOS app edit

curprev 06:5006:50, 27 April 2022‎ SpiralSource talk contribs‎ m 12,031 bytes −27‎ →‎In acyclic directed graphs: brevity undo Tag: Visual edit

curprev 11:3711:37, 26 April 2022‎ SpiralSource talk contribs‎ 12,058 bytes +25‎ →‎In acyclic directed graphs undo Tag: Visual edit
curprev 11:3611:36, 26 April 2022‎ SpiralSource talk contribs‎ 12,033 bytes +597‎ Added information about graph theory undo Tag: Visual edit

curprev 02:3002:30, 25 May 2021‎ Fawly talk contribs‎ 11,436 bytes +45‎ add link undo Tag: 2017 wikitext editor

curprev 02:3502:35, 4 May 2021‎ Beland talk contribs‎ m 11,391 bytes −5‎ convert special characters (via WP:JWB) undo

curprev 05:0005:00, 14 December 2020‎ Misof talk contribs‎ m 11,396 bytes +9‎ Slight improvement to phrasing. Notably, the "its" could be read as talking about a new transitive reduction of the transitive closure and not the original one. undo
curprev 04:5304:53, 14 December 2020‎ Misof talk contribs‎ 11,387 bytes +21‎ Fixed the definition. (Wow, how did this bug remain undetected? The second paragraph got it right but the first didn't. The Aho et al definition has equivalence, and it matters.) undo

curprev 19:0519:05, 25 November 2020‎ 84.245.120.59 talk‎ 11,366 bytes +3‎ →‎In graphs with cycles: the reduction can be unique in cyclic graphs; namely in all those which are transitive reductions of themselves undo

curprev 22:3122:31, 22 September 2020‎ David Eppstein talk contribs‎ 11,363 bytes −16‎ We don't have to waffle so much: when there is a cycle, the reduction is never unique undo
curprev 22:2222:22, 22 September 2020‎ 2001:56a:72e9:d900:9ca3:8538:9a8b:dc89 talk‎ 11,379 bytes +12‎ →‎In graphs with cycles undo

curprev 20:0520:05, 26 May 2020‎ A3nm talk contribs‎ 11,367 bytes +12‎ →‎In graphs with cycles: redirect to right section undo Tag: 2017 wikitext editor

curprev 13:1413:14, 23 April 2020‎ 147.229.208.56 talk‎ 11,355 bytes +76‎ Rephrasing to a more understandabe formulation, akin to the original one from 02:13, 16 January 2013. Yes David, I did notice that the total time bound is O(mn), but the mention of "linear-time" in the sentence confused me. undo

curprev 04:0004:00, 19 April 2020‎ David Eppstein talk contribs‎ 11,279 bytes +50‎ Undid revision 951811896 by 147.229.208.56 (talk) You did notice that the total time bound is O(mn), no? undo Tag: Undo
curprev 01:0301:03, 19 April 2020‎ 147.229.208.56 talk‎ 11,229 bytes −50‎ Removed an "implementation detail" which was somewhat confusing. The search would presumably not be started from each vertex separately, but *only* from a single vertex (the topologically greatest or least); otherwise it's hard to imagine how a linear time bound could be achieved. undo
curprev 00:5700:57, 19 April 2020‎ 147.229.208.56 talk‎ 11,279 bytes +34‎ made deep link (longest path distance => longest path distance in DAGs) undo

curprev 03:0703:07, 17 April 2020‎ David Eppstein talk contribs‎ 11,245 bytes 0‎ fix broken harv link undo
curprev 03:0603:06, 17 April 2020‎ David Eppstein talk contribs‎ 11,245 bytes −107‎ Undo drive-by tags. This is not an algorithms textbook — worked examples are a bad idea, per WP:NOTTEXTBOOK, and the matrix multiplication bound is immediately above in the same section. If comparing two explicitly-stated time bounds is too tricky, you're not ready for this material. undo
curprev 02:1402:14, 17 April 2020‎ 147.229.208.56 talk‎ 11,352 bytes 0‎ fullstop *before* tag undo

curprev 04:0504:05, 3 February 2020‎ AnomieBOT talk contribs‎ m 11,352 bytes +76‎ Dating maintenance tags: {{Examples}} {{Confusing}} {{Cn}} {{Explain}} undo
curprev 02:0502:05, 3 February 2020‎ 147.229.208.56 talk‎ 11,276 bytes +12‎ →‎Computing the reduction in sparse graphs undo
curprev 02:0402:04, 3 February 2020‎ 147.229.208.56 talk‎ 11,264 bytes +19‎ →‎Computing the reduction in sparse graphs undo

curprev 20:5820:58, 2 August 2018‎ Gymel talk contribs‎ m 11,245 bytes +11‎ confined IW link undo

curprev 18:5618:56, 19 February 2018‎ BarroColorado talk contribs‎ 11,234 bytes +17‎ emphasize that this is valid only for DAGs (mentioned in previous section, but easy to miss) →‎Computing the reduction using the closure undo

curprev 15:2515:25, 12 October 2017‎ 23.17.5.54 talk‎ 11,217 bytes −1‎ fix small typo undo

19 September 2024

28 May 2024

13 February 2024

24 October 2023

8 September 2023

12 August 2023

20 April 2023

2 March 2023

17 October 2022

1 September 2022

26 June 2022

27 April 2022

26 April 2022

25 May 2021

4 May 2021

14 December 2020

25 November 2020

22 September 2020

26 May 2020

23 April 2020

19 April 2020

17 April 2020

3 February 2020

2 August 2018

19 February 2018

12 October 2017