ABSTRACT
Our aim in this chapter is to discover and construct subgraphs in a complex network that may be attributed to some special function about the structure of that network. We have already described some of these structures in relation to the complexity of the algorithms; here, our aim is to investigate efficient approximate and heuristic algorithms for the solutions to these problems. We start with the independent set which consists of a subset of the vertices of a graph such that no member of this set is a neighbor to another vertex in this set. The second special group of vertices in a graph called a dominating set consists of a subset of vertices of a graph G such that each vertex of G is either in this set or a neighbor of a vertex in this set. We will see that these two concepts are related. We then investigate the matching in a graph which consists of a subset of edges of the graph where any vertex incident to an edge of matching is not a neighbor to any other vertex incident to another edge of the matching. Finally, we look into the vertex cover that is a subset of vertices such that each edge of the graph is incident to at least one vertex in this set. For each problem described, efficient sequential algorithms are provided and for the case of computer networks, we show the implementation of a sample distributed algorithm to construct a vertex cover. These special subgraphs are mainly used to find clusters and also for various other applications in complex networks.
