Back to Search
Start Over
On the Threshold of Having a Linear Treewidth in Random Graphs.
On the Threshold of Having a Linear Treewidth in Random Graphs.
- Source :
- Computing & Combinatorics (9783540369257); 2006, p226-234, 9p
- Publication Year :
- 2006
-
Abstract
- The concept of tree-width and tree-decomposition of a graph plays an important role in algorithms and graph theory. Many NP-hard problems have been shown to be polynomially sovable when restricted to the class of instances with a bounded tree-width. In this paper, we establish an improved lower bound on the threshold for a random graph to have a linear treewidth, which improves the previous result by Kloks [1]. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISBNs :
- 9783540369257
- Database :
- Complementary Index
- Journal :
- Computing & Combinatorics (9783540369257)
- Publication Type :
- Book
- Accession number :
- 32887312
- Full Text :
- https://doi.org/10.1007/11809678_25