LCS Technical Reports (1974 - 2003): Recent submissions
Now showing items 7-9 of 666
-
Fixed Parameter Algorithms for Minor-Closed Graphs (of Locally Bounded Treewidth)
(2003-06)Frick and Grohe showed that for each property phi that is definable in first-order logic, and for each class of minor-closed graphs of locally bounded treewidth, there is an O(n^(1+epsilon))-time algorithm deciding whether ... -
Equivalence of Local Treewidth and Linear Local Treewidth and its Algorithmic Applications
(2003-05)We solve an open problem posed by Eppstein in 1995 and re-enforced by Grohe concerning locally bounded treewidth in minor-closed families of graphs. A graph has bounded local treewidth if the subgraph induced by vertices ...
