The Library
Tree-width and optimization in bounded degree graphs
Tools
Lozin, Vadim V. and Milanic, Martin (2007) Tree-width and optimization in bounded degree graphs. In: Brandstadt, A. and Kratsch, D. and Muller, H., (eds.) Graph-Theoretic Concepts in Computer Science :33rd International Workshop, WG 2007, Dornburg, Germany, June 21-23, 2007. Revised Papers. Lecture Notes in Computer Science, Volume 4769 . Berlin Heidelberg: Springer Verlag, pp. 45-54. ISBN 9783540748380
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1007/978-3-540-74839-7
Abstract
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: | Book Item | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Series Name: | Lecture Notes in Computer Science | ||||
Journal or Publication Title: | GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE | ||||
Publisher: | Springer Verlag | ||||
Place of Publication: | Berlin Heidelberg | ||||
ISBN: | 9783540748380 | ||||
ISSN: | 0302-9743 | ||||
Book Title: | Graph-Theoretic Concepts in Computer Science :33rd International Workshop, WG 2007, Dornburg, Germany, June 21-23, 2007. Revised Papers | ||||
Editor: | Brandstadt, A. and Kratsch, D. and Muller, H. | ||||
Official Date: | 2007 | ||||
Dates: |
|
||||
Volume: | Volume 4769 | ||||
Number of Pages: | 10 | ||||
Page Range: | pp. 45-54 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Conference Paper Type: | Paper | ||||
Title of Event: | 33rd International Workshop on Graph-Theoretic Concepts in Computer Science | ||||
Type of Event: | Workshop | ||||
Location of Event: | Dornburg, Germany | ||||
Date(s) of Event: | 21-23 Jun 2007 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |