THE ALGORITHMIC USE OF HYPERTREE STRUCTURE AND MAXIMUM NEIGHBORHOOD ORDERINGS

The use of (generalized) tree structure in graphs is one of the main t opics in the field of efficient graph algorithms. The well-known parti al k-tree (resp. treewidth) approach belongs to this kind of research and bases on a tree structure of constant-size bounded maximal cliques . Without size bound on the cliques this tree structure of maximal cli ques characterizes chordal graphs which are known to be important also in connection with relational database schemes where hypergraphs with tree structure (acyclic hypergraphs) and their elimination orderings (perfect elimination orderings for chordal graphs, Graham-reduction fo r acyclic hypergraphs) are studied. We consider here graphs with a tre e structure which is dual (in the sense of hypergraphs) to that one of chordal graphs (therefore we call these graphs dually chordal). The c orresponding vertex elimination orderings of these graphs are the maxi mum neighbourhood orderings. These orderings were studied recently in several papers and some of the algorithmic consequences of such orderi ngs are given. The aim of this paper is a systematic treatment of the algorithmic use of maximum neighbourhood orderings. These orderings ar e useful especially for dominating-like problems (including Steiner tr ee) and distance problems. Many problems efficiently solvable for stro ngly chordal and doubly chordal graphs remain efficiently solvable for dually chordal graphs too. Our results on dually chordal graphs not o nly generalize, but also improve and extend the corresponding results on strongly chordal and doubly chordal graphs, since a maximum neighbo urhood ordering (if it exists) can be constructed in linear time and w e consequently use the underlying structure properties of dually chord al graphs closely connected to hypergraphs. Furthermore, a collection of problems remaining NP-complete on dually chordal graphs is given. ( C) 1998 Elsevier Science B.V. All rights reserved.