Treewidth: 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 10:0410:04, 11 November 2024 Fatupha talk contribs 42,480 bytes +10 Fixed ambiguity: there are graphs of tw 2 that are not sp-graphs (see linked article for source) undo Tags: Mobile edit Mobile web edit

curprev 13:0113:01, 12 August 2024 Citation bot talk contribs 42,470 bytes +107 Added isbn. | Use this bot. Report bugs. | Suggested by Abductive | Category:NP-complete problems | #UCB_Category 125/181 undo

curprev 07:2107:21, 31 July 2024 David Eppstein talk contribs 42,363 bytes −249 better ref per talk undo
curprev 05:5505:55, 31 July 2024 2a02:8071:8284:50a0::1530 talk 42,612 bytes 0 No edit summary undo
curprev 05:5105:51, 31 July 2024 2a02:8071:8284:50a0::1530 talk 42,612 bytes 0 No edit summary undo
curprev 05:4905:49, 31 July 2024 2a02:8071:8284:50a0::1530 talk 42,612 bytes +273 No edit summary undo

curprev 08:5008:50, 16 July 2024 666-Bandera Mouse talk contribs 42,339 bytes +34 No edit summary undo

curprev 19:1919:19, 10 April 2024 Paditor talk contribs m 42,305 bytes +1 →Courcelle's theorem: Add missing space undo Tag: Visual edit: Switched

curprev 07:2807:28, 4 March 2024 T.seppelt talk contribs 42,304 bytes 0 →Forbidden minors: the claimed statements are not in Bodlaender (1988) but in Bodlaender (1998) undo

curprev 13:1113:11, 2 January 2024 T.seppelt talk contribs m 42,304 bytes +4 →Computing the treewidth: format undo

curprev 06:1306:13, 25 December 2023 OAbot talk contribs m 42,300 bytes +21 Open access bot: doi updated in citation with #oabot. undo

curprev 14:4314:43, 31 July 2023 Andy02124 talk contribs m 42,279 bytes 0 sfn fix (date) undo

curprev 22:1622:16, 13 February 2023 Headbomb talk contribs 42,279 bytes +117 Add: s2cid, arxiv, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this tool. Report bugs. | #UCB_Gadget | Alter: template type. Add: eprint, class. Removed parameters. Some additions/deletions were parameter name changes. | Use this tool. Report bugs. | #UCB_Gadget undo

curprev 01:3601:36, 5 December 2022 WikiCleanerBot talk contribs m 42,162 bytes 0 v2.05b - Bot T20 CW#61 - Fix errors for CW project (Reference before punctuation) undo Tag: WPCleaner

curprev 03:1803:18, 28 November 2022 Uaibuff talk contribs 42,162 bytes −38 Moved discussion on search-based algorithm to the appropriate section. undo Tag: Visual edit

curprev 19:2319:23, 27 November 2022 David Eppstein talk contribs 42,200 bytes −3 Undid revision 1124070128 by Uaibuff (talk) grammatical disimprovement undo Tag: Undo
curprev 05:0805:08, 27 November 2022 Uaibuff talk contribs m 42,203 bytes +3 →Anytime Search-Based Algorithms: (Fixed grammar errors) undo Tags: Reverted Visual edit
curprev 05:0605:06, 27 November 2022 Uaibuff talk contribs 42,200 bytes +1,963 Added description about search-based algorithms for computing treewidth. undo Tag: Visual edit

curprev 01:2301:23, 21 November 2022 Mahdibelly talk contribs m 40,237 bytes 0 →References: typo undo
curprev 01:2201:22, 21 November 2022 Mahdibelly talk contribs 40,237 bytes +192 →References: added korhonen-lokshtanov reference undo
curprev 01:1701:17, 21 November 2022 Mahdibelly talk contribs m 40,045 bytes +25 →Algorithms: typo in writing epsilon undo
curprev 01:1401:14, 21 November 2022 Mahdibelly talk contribs 40,020 bytes +274 →Algorithms: added korhonen-lokshtanov 2^(k^2)poly(n) algoroithm to the table. undo

curprev 02:5902:59, 19 September 2022 71.58.108.84 talk 39,746 bytes 0 →Algorithms: In my previous edit I wrote "l" instead of "k" (fixed a typo in Reed's row) undo
curprev 02:5802:58, 19 September 2022 71.58.108.84 talk 39,746 bytes +24 →Algorithms: Someone had swapped Lagergren's and Reed's running time! I also added the possibility of 7-approximation for Reed's algorithm however with a tiny justification one can prove that it in fact is a 5-approximation ("An Improvement of Reed's Treewidth Approximation") and Reed claims so too (however, he does not prove it precisely). undo

curprev 15:2615:26, 15 September 2022 TheMathCat talk contribs 39,722 bytes +48 wikilinks undo

curprev 14:1814:18, 26 August 2022 2601:199:c301:13e0::ab02 talk 39,674 bytes +47 inserted "in terms of" where a previous edit had (inappropriately) removed "from" undo

curprev 14:3414:34, 20 July 2022 Felix Schroeder talk contribs m 39,627 bytes −1 →Algorithms: just removed an off parenthesis undo
curprev 14:3314:33, 20 July 2022 Felix Schroeder talk contribs 39,628 bytes −7 →Computing the treewidth: consolidated text and table, a look in the paper tells me, the table is right, not the text. Also simplified O-Notation. undo
curprev 14:3114:31, 20 July 2022 Felix Schroeder talk contribs 39,635 bytes +7 →Grid minor size: changed the definition of f, so the context is correct. undo

curprev 14:5514:55, 8 July 2022 David Eppstein talk contribs 39,628 bytes +21 →Hadwiger number and S-functions: universal vertex undo

curprev 22:4122:41, 4 July 2022 OlliverWithDoubleL talk contribs 38,949 bytes +130 math formatting undo Tags: Mobile edit Mobile app edit iOS app edit

curprev 03:0103:01, 16 June 2022 OlliverWithDoubleL talk contribs m 38,819 bytes −24 Fixed typo undo Tags: Mobile edit Mobile app edit iOS app edit
curprev 03:0003:00, 16 June 2022 OlliverWithDoubleL talk contribs 38,843 bytes +127 short description, links undo Tags: Mobile edit Mobile app edit iOS app edit

curprev 13:1613:16, 27 March 2022 Tuukka Korhonen talk contribs 38,716 bytes 0 Fixed the dependency on k in Bodlaender's algorithm from k^O(k^3) to 2^O(k^3). The incorrect time complexity was probably propagated from a mistake in Bodlaender et al. 2016. The correct time complexity is already explicitly mentioned in Bodlaender 1996 in the end of section 6. undo
curprev 13:0713:07, 27 March 2022 109.189.157.235 talk 38,716 bytes +202 Updated the reference to my paper. undo

curprev 08:0208:02, 2 February 2022 David Eppstein talk contribs 38,514 bytes +2,152 restore consistent citation style and alphabetization; fix odd Lagergren/Reed misauthorship; fix missing metadata from Amir; format math in titles; update two arxiv preprints; add journal links undo

curprev 16:0616:06, 1 February 2022 104.39.135.51 talk 36,362 bytes +9 →Computing the treewidth: edited the dependence on n in Amir's second result. It was mistakenly written n^2 undo

curprev 19:0819:08, 5 November 2021 Mahdibelly talk contribs m 36,353 bytes +56 →References: fixed the title of Belbasi-Furer n logn 2021 reference undo
curprev 19:0619:06, 5 November 2021 Mahdibelly talk contribs m 36,297 bytes +126 →References: added Belbasi-Furer n logn 2021 reference undo
curprev 19:0219:02, 5 November 2021 Mahdibelly talk contribs 36,171 bytes +116 →Computing the treewidth: I added Belbasi-Fürer 2021 n logn result undo

curprev 02:3902:39, 29 October 2021 Dicklyon talk contribs m 36,055 bytes +4 dash fix (via WP:JWB) undo

curprev 14:2014:20, 4 October 2021 Mahdibelly talk contribs m 36,051 bytes −40 →Computing the treewidth undo

curprev 08:3608:36, 24 September 2021 Tuukka Korhonen talk contribs 36,091 bytes −33 I mentioned this bound only as a brief, informal side note in a talk. I also said to not take this bound seriosly, it was only a rough estimation. Also, in any case it does not make sense to specify only omega-notation when talking about worst-case bounds. undo

curprev 01:3901:39, 17 September 2021 Mahdibelly talk contribs m 36,124 bytes +1 →Computing the treewidth: fixed a typo (space) undo
curprev 01:3801:38, 17 September 2021 Mahdibelly talk contribs m 36,123 bytes −7 →Computing the treewidth undo

11 November 2024

12 August 2024

31 July 2024

16 July 2024

10 April 2024

4 March 2024

2 January 2024

25 December 2023

31 July 2023

13 February 2023

5 December 2022

28 November 2022

27 November 2022

21 November 2022

19 September 2022

15 September 2022

26 August 2022

20 July 2022

8 July 2022

5 July 2022

4 July 2022

16 June 2022

27 March 2022

2 February 2022

1 February 2022

5 November 2021

29 October 2021

4 October 2021

24 September 2021

17 September 2021