A partial ordering of the chordal graphs

Rasmussen, Craig W.; Carroll, Thomas

dc.contributor.author	Rasmussen, Craig W.
dc.contributor.author	Carroll, Thomas
dc.date.accessioned	2012-11-01T22:59:04Z
dc.date.available	2012-11-01T22:59:04Z
dc.date.issued	1997-02
dc.identifier.uri	https://hdl.handle.net/10945/15329
dc.description.abstract	The chordal graphs have been well-studied because of their desirable algorithmic characteristics. Many problems that are intractable in the general case are solvable by fast algorithms in the chordal case. We show that the chordal graphs are partially ordered under edge set inclusion, and describe algorithms for bidirectional traversal of maximal chains in the corresponding cover graph. We also describe the embedding of several subclasses of the chordal graphs as subposets of the chordal poset, and suggest application of these order relations to the design of improved heuristics for obtaining approximate solutions to problems on arbitrary graphs.	en_US
dc.publisher	Monterey, California. Naval Postgraduate School	en_US
dc.title	A partial ordering of the chordal graphs	en_US
dc.type	Technical Report	en_US
dc.contributor.department	Electrical and Computer Engineering
dc.subject.author	Algorithms.	en_US
dc.subject.author	Signal processing.	en_US
dc.subject.author	Loran.	en_US
dc.subject.author	Kalman filtering.	en_US
dc.identifier.oclc	ocm294961696
dc.identifier.npsreport	NPS-MA-97-002
dc.description.distributionstatement	Approved for public release; distribution is unlimited.