TY - JFULL
AU - Swapnil Gupta and C. Pandu Rangan
PY - 2016/7/
TI - Computing Maximum Uniquely Restricted Matchings in Restricted Interval Graphs
T2 - International Journal of Computer and Information Engineering
SP - 979
EP - 989
VL - 10
SN - 1307-6892
UR - https://publications.waset.org/pdf/10004512
PU - World Academy of Science, Engineering and Technology
NX - Open Science Index 114, 2016
N2 - A uniquely restricted matching is defined to be a
matching M whose matched vertices induces a sub-graph which has
only one perfect matching. In this paper, we make progress on the
open question of the status of this problem on interval graphs (graphs
obtained as the intersection graph of intervals on a line). We give
an algorithm to compute maximum cardinality uniquely restricted
matchings on certain sub-classes of interval graphs. We consider two
sub-classes of interval graphs, the former contained in the latter, and
give O(|E|^2) time algorithms for both of them. It is to be noted that
both sub-classes are incomparable to proper interval graphs (graphs
obtained as the intersection graph of intervals in which no interval
completely contains another interval), on which the problem can be
solved in polynomial time.
ER -