The Properties Of The Orderings And The Last Vertices Induced By Maximal Neighborhood Search Algorithm

This paper is about the properties of Maximal Neighborhood Search algorithm (sim-plified as MNS), and we focused our attention on the properties of the orderings induced by MNS algorithm and the last vertices of these orderings. First, we analyzed the similar-ity among MNS algorithm, LexBFS algorithm, MCS algorithm and LexDFS algorithm. By using the similar method with other algorithms, we found out that not every MNS ordering in chordal graphs is an moplex elimination ordering. This property of MNS algorithm is totally different from other algorithms.In order to find minimal separators and maximal cliques of graphs, considering the special properties of MNS algorithm, we did our research with the help of the label search pattern. We realized that when the labels of two adjacent vertices of an MNS ordering hold some special conditions, we can get the minimal separator by the label of the later vertex of those two vertices and the maximal clique by the former vertex’s label. We proved this property by mathematical induction. Meanwhile, we gave some counter examples to show this method is not functioned on non-chordal graphs.Last but not the least, we studied the last vertices of these MNS orderings, and got the property that in chordal graphs the last vertices of MNS orderings must belong to some molpex. However, this property is not true in non-chordal graphs.