Back close

Heuristic for Maximum Matching in Directed Complex Networks

Publication Type : Conference Paper

Publisher : IEEE

Source : Accepted in ICACCI 2013.

Url :

Campus : Amritapuri

School : School of Computing

Verified : No

Year : 2013

Abstract : Determining maximum matching in any network has always been a problem of immense concern. Its solution is a necessary requirement in structural control theory for controlling real world complex networks. The prevalent classical approach through the Hopcroft-Karp algorithm and other proposed algorithms require the determination of the bipartite equivalent graph (i.e., network), which belongs to the NP-complete class of problems. In this article, we develop a degree-first greedy search algorithm to determine maximum matching in unipartite graphs without determining its bipartite equivalent. Thus this classical problem of the NP-Complete class can be solved using the heuristic, with reduced complexity. This algorithm can be efficiently used to find maximum matching in most of the real world complex networks which follow Erdos-Rényi model. Simulation results obtained using our heuristic show that dense and homogenous networks can be controlled with fewer controller nodes popularly termed as driver nodes, compared to the sparse inhomogeneous networks.

Cite this Research Publication : A. Chatterjee, D. Das, N. Bhowmick, A. Mukherjee, M. K. Naskar, "Heuristic for Maximum Matching in Directed Complex Networks", Accepted in ICACCI 2013.

Admissions Apply Now