Level-treewidth property, exact algorithms and approximation schemes
Description:
Informally, a class of graphs Q is said to have the level-treewidth property (LT-property) if for every G {element_of} Q there is a layout (breadth first ordering) L{sub G} such that the subgraph induced by the vertices in k-consecutive levels in the layout have treewidth O(f (k)), for some function f. We show that several important and well known classes of graphs including planar and bounded genus graphs, (r, s)-civilized graphs, etc, satisfy the LT-property. Building on the recent work, we p…
more
Date:
June 1, 1997
Creator:
Marathe, M. V.; Hunt, H. B. & Stearns, R. E.
Item Type:
Refine your search to only
Article
Partner:
UNT Libraries Government Documents Department