Timeline for Logspace algorithms on graphs with bounded tree width
Current License: CC BY-SA 2.5
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 14, 2010 at 23:05 | vote | accept | Shiva Kintali | ||
| Oct 21, 2010 at 23:05 | comment | added | Yaroslav Bulatov | Makowski says that "all the graph polynomials studied in the literature are SOL-definable", and gives a formulation of Tutte polynomial in terms of SOL, page 15 of "From a Zoo to a Zoology: Towards a General Theory of Graph Polynomials." In "Algorithmic uses of the Feferman-Vaught theorem" he extends Courcelle's theorem to show tractability for SOL-definable polynomials on bounded tree-width graphs. | |
| Oct 20, 2010 at 3:12 | comment | added | Hsien-Chih Chang 張顯之 | According to the paper, it is a function in $k$ with order about $O(2^{(k^{3+\epsilon})})$. | |
| Oct 20, 2010 at 3:02 | comment | added | Michael Blondin | What is the function f? | |
| Oct 20, 2010 at 2:33 | history | answered | Hsien-Chih Chang 張顯之 | CC BY-SA 2.5 |