| Home | << 1 >> |
|
| Record | |||||
|---|---|---|---|---|---|
| Author | Ortiz, C.; Villanueva, M. | ||||
| Title | Maximal independent sets in caterpillar graphs | Type | |||
| Year | 2012 | Publication  |
Discrete Applied Mathematics | Abbreviated Journal | Discret Appl. Math. |
| Volume | 160 | Issue | 3 | Pages | 259-266 |
| Keywords | Graph algorithms; Caterpillar graph; Enumeration of maximal independent sets; Intersection graph; Independent graph; Clique graph | ||||
| Abstract | A caterpillar graph is a tree in which the removal of all pendant vertices results in a chordless path. In this work, we determine the number of maximal independent sets (mis) in caterpillar graphs. For a general graph, this problem is #P-complete. We provide a polynomial time algorithm to generate the whole family of mis in a caterpillar graph. We also characterize the independent graph (intersection graph of mis) and the clique graph (intersection graph of cliques) of complete caterpillar graphs. (C) 2011 Elsevier B.V. All rights reserved. | ||||
| Address | [Villanueva, Monica] Univ Santiago Chile, Fac Engn, Santiago, Chile, Email: monica.villanueva@usach.cl | ||||
| Corporate Author | Thesis | ||||
| Publisher | Elsevier Science Bv | Place of Publication | Editor | ||
| Language | English | Summary Language | Original Title | ||
| Series Editor | Series Title | Abbreviated Series Title | |||
| Series Volume | Series Issue | Edition | |||
| ISSN | 0166-218x | ISBN | Medium | ||
| Area | Expedition | Conference | |||
| Notes | WOS:000299144900009 | Approved | |||
| Call Number | UAI @ eduardo.moreno @ | Serial | 190 | ||
| Permanent link to this record | |||||