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.

Authors :
Chen, Danny Z.
Lee, D. T.
Gao, Yong
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