FIC-UAI Publication Database -- Query Results

	FIC-UAI Publication Database Home \| Show All \| Simple Search \| Advanced Search	Login Quick Search: Field: contains: ...
	1-1 of 1 record found matching your query:

Search & Display Options

Select All Deselect All

<< 1 >>

|

|

Details

	Record						Links
	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

Select All Deselect All

<< 1 >>

|

|

Details

All Found Records Selected Records:

Save Citations: Format:

Export Records: Format:

CQL Search | Library Search | Show Record | Extract Citations