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.

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:	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
Publisher:	SPRINGER-VERLAG BERLIN
ISBN:	978-3-540-74838-0
ISSN:	0302-9743
Editor:	Brandstadt, A and Kratsch, D and Muller, H
Date:	2007
Volume:	4769
Number of Pages:	10
Page Range:	pp. 45-54
Publication Status:	Published
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
URI:	http://wrap.warwick.ac.uk/id/eprint/30636

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item