The Library
From tree-width to clique-width : excluding a unit interval graph
Tools
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. ISBN 978-3-540-92181-3. doi:10.1007/978-3-540-92182-0 ISSN 0302-9743.
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-92182-0
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, Engineering and Medicine > 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 | ||||
Official Date: | 2008 | ||||
Dates: |
|
||||
Volume: | Vol.5369 | ||||
Number of Pages: | 12 | ||||
Page Range: | pp. 871-882 | ||||
DOI: | 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 |
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 |