Loading...
Please wait, while we are loading the content...
Similar Documents
A Note on Treewidth Pathwidth and Cutwidth *
| Content Provider | Semantic Scholar |
|---|---|
| Author | Korach, Ephraim Nir Sole I. |
| Copyright Year | 2014 |
| Abstract | Let tw(G), pw(G), c(G), !J.(G) denote, respectively, the tree-width, path-width, cutwidth and the maximum degree of a graph G on 11 vertices . It is known that c (G)~tw (G). We prove that c (G) =0 (tw (G)·!J.(G)·logn), and if ({Xj : iel] ,T=(I,A» is a tree decomposition of G with tree-wid~ then c (G) S (k+ l)·!J.(G)·c (T). In case that a tree decomposition is given, or that the tree-width is bounded by a constant, efficient algorithms for finding a numoering with cutwidth within the upper bounds are implicit in the proofs. We obtain the above results by showing that pw(G)=O(log n·tw(G», and pw (G )!:(k+1)·c (T). |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/1990/CS/CS0648.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
