The algorithmic use of hypertree structure and maximum neighbourhood orderings (Q1383368): Difference between revisions

Graphs with a tree structure which are dual (in the sense of hypergraphs) to the ones of chordal graphs are studied. These graphs are called dually chordal. The corresponding vertex elimination orderings of dually chordal graphs are the maximum neighbourhood orderings. In this paper, a systematic treatment of the algorithmic applications of maximum neighbourhood orderings is undertaken. These orderings are useful, especially for dominating-like and distance problems.