Uniquely Restricted Matchings in a Graph

• Download source code - 12.9 KB

Introduction

The code is written in C language using Dev C++ tool. The code reads a graph from the file which is presented in as adjacency list. Then, it finds all the matching present in the graph. Then it filters out the uniquely restricted matching from the previous matching list.

Background 

A matching in a graph is a set of edges no two of which share a common vertex. A uniquely restricted matching in a graph is a matching M whose saturated vertices induce a subgraph which has only one perfect matching,which is M itself. The developed algorithm finds all the matching present in the graph and then finds the uniquely restricted matching. 

Using the code

Just a double-click on the mouse pad will do the job. Then enter the file-name to read the graph. There are 6 testcases given with the code. You may test others too, but with the same input structure for the graph in the text file.A brief description of how to use the article or code. The number in the first line is the no. of vertices present in the graph. Then the 1st numbers in each line are the vertex ids and the numbers next to them are the adjacent vertices to the 1st vertex i.e. the 1st number.

History

1.0.