Determining All Maximum Uniquely Restricted Matching in Bipartite Graphs

Details Determining All Maximum Uniquely Restricted Matching in Bipartite Graphs Determining All Maximum Uniquely Restricted Matching in Bipartite Graphs

2010-09-28

arxiv.org/abs/1009.5435v1

Computer Science

Computational Complexity

9 pages, 5 figures

Scientific paper

The approach mapping from a matching of bipartite graphs to digraphs has been successfully used for forcing set problem, in this paper, it is extended to uniquely restricted matching problem. We show to determine a uniquely restricted matching in a bipartite graph is equivalent to recognition a acyclic digraph. Based on these results, it proves that determine the bipartite graphs with all maximum matching are uniquely restricted is polynomial time. This answers an open question of Levit and Mandrescu(Discrete Applied Mathematics 132(2004) 163-164).

Affiliated with

Also associated with

No associations

Rating

Determining All Maximum Uniquely Restricted Matching in Bipartite Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Determining All Maximum Uniquely Restricted Matching in Bipartite Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Determining All Maximum Uniquely Restricted Matching in Bipartite Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-693144