Timeline for The origin of the notion of treewidth
Current License: CC BY-SA 2.5
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 10, 2011 at 3:42 | comment | added | Akash Kumar | Sorry Mr. Gruber for this super-late reaction. I saw your answer long time back, was not sure if I could make other answers accepted after I had accepted one already. Your response is pretty accurate and looks dead on as noted by Mr. Salamon as well | |
| Apr 10, 2011 at 3:40 | vote | accept | Akash Kumar | ||
| Nov 3, 2014 at 21:52 | |||||
| Feb 25, 2011 at 23:46 | comment | added | András Salamon | Seems pretty accurate. From Diestel 3rd (English) edition pp.354–355: "The notions of tree-decomposition and tree-width were first introduced (under different names) by R. Halin, S-functions for graphs, J. Geometry 8 (1976), 171–186. Among other things, Halin showed that grids can have arbitrarily large tree-width. Robertson & Seymour reintroduced the two concepts, apparently unaware of Halin’s paper, with direct reference to K. Wagner, Über eine Eigenschaft der ebenen Komplexe, Math. Ann. 114 (1937), 570–590. (This is the seminal paper that introduced simplicial tree-decompositions" | |
| Feb 24, 2011 at 19:48 | history | answered | Hermann Gruber | CC BY-SA 2.5 |