Timeline for Logspace algorithms on graphs with bounded tree width
Current License: CC BY-SA 2.5
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 14, 2010 at 23:05 | vote | accept | Shiva Kintali | ||
| Oct 23, 2010 at 5:47 | history | edited | Kaveh |
edited tags
|
|
| Oct 20, 2010 at 2:33 | answer | added | Hsien-Chih Chang 張顯之 | timeline score: 15 | |
| Sep 16, 2010 at 14:06 | comment | added | gphilip | We can, in general, do better than $O(\sqrt{\log n})$ in approximating treewidth. The best polynomial-time approximation algorithm that I am aware of achieves an $O(\sqrt{\log w})$ approximation factor, where $w$ is the treewidth of the graph. See Feige, Hajiaghayi, and Lee, Improved approximation algorithms for minimum-weight vertex separators , STOC 2005. | |
| Sep 16, 2010 at 3:03 | comment | added | Shiva Kintali | $n$ is the number of vertices in the input graph. | |
| Sep 16, 2010 at 2:37 | comment | added | gphilip | What is the $n$ mentioned in the approximation factor? | |
| Sep 16, 2010 at 0:37 | history | asked | Shiva Kintali | CC BY-SA 2.5 |