Happy that our paper with Ariel Fernandez & Ryszard Janicki will appear in IJCA

Very happy that our paper Computing covers from matchings with permutations, with Ariel Fernández and Ryszard Janicki, is going to appear in the International Journal of Computer Applications.

We present a matrix permutation algorithm for computing a minimal vertex cover from a maximal matching in a bipartite graph. Our algorithm is linear time and linear space, and provides an interesting perspective on a well known problem. Unlike most algorithms, it does not use the concept of alternating paths, and it is formulated entirely in terms of combinatorial operations on a binary matrix. The algorithm relies on permutations of rows and columns of a 0-1 matrix which encodes a bipartite graph together with its maximal matching. This problem has many important applications such as network switches which essentially compute maximal matchings between their incoming and outgoing ports.

Share

Leave a Reply

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