Accession Number : ADA322752

Title :   A Partial Ordering of the Chordal Graphs.

Descriptive Note : Technical rept. Jan-Mar 96,

Corporate Author : NAVAL POSTGRADUATE SCHOOL MONTEREY CA DEPT OF MATHEMATICS

Personal Author(s) : Rasmussen, Criag W. ; Carroll, Thomas

PDF Url : ADA322752

Report Date : 07 FEB 1997

Pagination or Media Count : 15

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.

Descriptors :   *ALGORITHMS, *GRAPHS, MATRICES(MATHEMATICS), HEURISTIC METHODS, SET THEORY.

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE