The Library
On the maximum independent set problem in subclasses of subcubic graphs
Tools
Lozin, Vadim V., Monnot, Jérôme and Ries, Bernard (2013) On the maximum independent set problem in subclasses of subcubic graphs. In: Lecroq , Thierry and Mouchard, Laurent , (eds.) Combinatorial Algorithms. Lecture Notes in Computer Science, Volume 8288 . Berlin Heidelberg: Springer, pp. 314-326. ISBN 9783642452789
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-642-45278-9_27
Abstract
It is known that the maximum independent set problem is NP-complete for subcubic graphs, i.e. graphs of vertex degree at most 3. Moreover, the problem is NP-complete for H-free subcubic graphs whenever H contains a connected component which is not a tree with at most 3 leaves. We show that if every connected component of H is a tree with at most 3 leaves and at most 7 vertices, then the problem can be solved for H-free subcubic graphs in polynomial time.
Item Type: | Book Item | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Series Name: | Lecture Notes in Computer Science | ||||
Publisher: | Springer | ||||
Place of Publication: | Berlin Heidelberg | ||||
ISBN: | 9783642452789 | ||||
ISSN: | 0302-9743 | ||||
Book Title: | Combinatorial Algorithms | ||||
Editor: | Lecroq , Thierry and Mouchard, Laurent | ||||
Official Date: | 2013 | ||||
Dates: |
|
||||
Volume: | Volume 8288 | ||||
Page Range: | pp. 314-326 | ||||
DOI: | 10.1007/978-3-642-45278-9_27 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Description: | |||||
Title of Event: | 24th International Workshop, IWOCA 2013 | ||||
Type of Event: | Conference | ||||
Location of Event: | Rouen, France | ||||
Date(s) of Event: | 10-12 Jul 2013 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |