Click here to Skip to main content
Click here to Skip to main content

Uniquely Restricted Matchings in a Graph

, 1 Nov 2012 CPOL
Rate this:
Please Sign up or sign in to vote.
Algorithm to find out all the Matchings and Uniquely Restricted Matchings in a Graph

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.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Mr. Subhendu Sekhar Behera pursued his Bachelor of Technology in the Dept. of Computer Science & Engineering at National Institute of Science and Technology, Berhampur, Orissa. . He has also won numerous coding competitions in C/JAVA language pan India. His research interests lie in the field of Pattern Recognition, Soft Computing and Algorithm Design.He has two journal and two conference papers to his credit

Comments and Discussions

 
-- There are no messages in this forum --
| Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.141223.1 | Last Updated 1 Nov 2012
Article Copyright 2012 by Subhendu Sekhar Behera
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid