Lozin, Vadim V. (2008) From tree-width to clique-width : excluding a unit interval graph. In: 19th International Symposium on Algorithms and Computations (ISAAC 2008), Gold Coast, Australia, Dec 15-17, 2008. Published in: Lecture Notes in Computer Science, Vol.5369 pp. 871-882.

Full text not available from this repository.

Abstract

From the theory of graph minors we know that the class of planar graphs is the only critical class with respect to tree-width, In the present paper, we reveal a critical class with respect to clique-width, a notion generalizing tree-width. This class is known in the. literature under different names, such as unit interval, proper interval or indifference graphs, and has important applications in various fields, including molecular biology. We prove that the unit interval graphs constitute a minimal hereditary class of unbounded clique-width. As an application, we show that LIST COLORING is fixed parameter tractable in the class of unit, interval graphs.

Item Type:	Conference Item (UNSPECIFIED)
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Science > Mathematics
Series Name:	LECTURE NOTES IN COMPUTER SCIENCE
Journal or Publication Title:	Lecture Notes in Computer Science
Publisher:	Springer
ISBN:	978-3-540-92181-3
ISSN:	0302-9743
Editor:	Hong, SH and Nagamochi, H and Fukunaga, T
Date:	2008
Volume:	Vol.5369
Number of Pages:	12
Page Range:	pp. 871-882
Identification Number:	10.1007/978-3-540-92182-0
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Title of Event:	19th International Symposium on Algorithms and Computations (ISAAC 2008)
Type of Event:	Conference
Location of Event:	Gold Coast, Australia
Date(s) of Event:	Dec 15-17, 2008
URI:	http://wrap.warwick.ac.uk/id/eprint/28307

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item