A node marking algorithm for partitioning wireless mesh networks

The usual search and traversal methods, like depth first search of graphs and the breadth first search of graphs, are based on marking the vertices as discovered, or visited, to avoid repetitions. This paper proposes a simple yet efficient and very low time complexity algorithm based on adjacency matrix to mark visited / selected vertices for a simple dense graph. This adjacency matrix based method is especially useful in relabeling of adjacency matrix for creating graph partitions. Relabeling is carried out to collect neighboring nodes and form a partition. This algorithm is generic and can be used for any adjacency matrix based graph search.