Tree-width and optimization in bounded degree graphs
Lozin, Vadim and Milanic, Martin (2007) Tree-width and optimization in bounded degree graphs. In: 33rd International Workshop on Graph-Theoretic Concepts in Computer Science, Dornburg, GERMANY, JUN 21-23, 2007. Published in: GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, 4769 pp. 45-54.Full text not available from this repository.
It is well known that boundedness of tree-width implies polynomial-time solvability of many algorithmic graph problems. The converse statement is generally not true, i.e., polynomial-time solvability does not necessarily imply boundedness of tree-width. However, in graphs of bounded vertex degree, for some problems, the two concepts behave in a more consistent way. In the present paper, we study this phenomenon with respect to three important graph problems - dominating set, independent dominating set and induced matching - and obtain several results toward revealing the equivalency between boundedness of the tree-width and polynomial-time solvability of these problems in bounded degree graphs.
|Item Type:||Conference Item (UNSPECIFIED)|
|Subjects:||Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software|
|Series Name:||LECTURE NOTES IN COMPUTER SCIENCE|
|Journal or Publication Title:||GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE|
|Editor:||Brandstadt, A and Kratsch, D and Muller, H|
|Number of Pages:||10|
|Page Range:||pp. 45-54|
|Title of Event:||33rd International Workshop on Graph-Theoretic Concepts in Computer Science|
|Location of Event:||Dornburg, GERMANY|
|Date(s) of Event:||JUN 21-23, 2007|
Actions (login required)