Volume 4, Issue 3, 2014

By | August 12, 2018

An O(n) Time Algorithm For Maximum Induced Matching In Bipartite Star123-free Graphs

Ruzayn Quaddoura, Department of Computer Science, Faculty of Science and Information Technology, Zarqa University, Zarqa-Jordan.

Abstract— 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.

Keywords-Bipartite graph; Decomposition of graphs; Design and analysis of algorithms; Matching; Induced Matching.

Dynamic Solutions for Leader Failure in 3D Torus Networks

Mohammed Refai, Al Zarqa University, College of Science and Information Technology.

Abstract— 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.

Keywords- Dynamic Leader Election; Intermittent Links Failure; Time Complexity; 3D Torus Networks.

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *