A matching in a graph is a set of edges no two of which share a common vertex. A matching M is an induced matching if no edge connects two edges of M. The problem of finding a maximum induced matching is known to be NP-hard in general and specifically for bipartite graphs. Lozin has been proposed an O(n^3) time algorithm for this problem on the class of bipartite 〖Star〗_123,〖Sun〗_4-free graphs. In this paper we improve and generalize this result in presenting a simple O(n) time algorithm for maximum induced matching problem in bipartite 〖Star〗_123-free graphs.
Leader election is a very important algorithm in wired and wireless networks. It is used to solve the single point failure in distributed systems when one process which called leader is responsible to coordinate and manage the whole network. The leader election algorithms (LEA's) solve the instability problem in the network, which caused by leader failure. The research work reported here is concerned with building and designing a dynamic leader election algorithm, to contribute in solving leader crash problem in three dimensional torus networks. The algorithm solves leader failure despite the existing of intermittent links failure. Algorithm performance was evaluated by calculating the number of messages and time steps overall the algorithm. In a network of N nodes connected by a three dimensional torus network, the performance is evaluated, when leader failure is detected by a (N-1) node and algorithm faces F link failure. The number of messages is O(N+F) in time steps.
Today
Yesterday
This week
This month
All days
Number of views: 365