Uniquely Restricted Matchings in Interval Graphs
Uniquely Restricted Matchings in Interval Graphs
复制标题
区间图中的唯一限制匹配
DOI：
--
复制
发表时间：
2016
影响因子：
0.8
通讯作者：
Satyabrata Jana
中科院分区：
文献类型：
--
作者：
Mathew C. Francis;Dalu Jacob;Satyabrata Jana
图$G$中的匹配$M$被认为是唯一受限的，如果$G$中没有其他匹配与$M$匹配相同的顶点集。我们描述了一个多项式时间算法来计算区间图中的最大基数唯一限制匹配，从而回答了Golumbic， Hirst和Lewenstein的问题[算法，31 (2001),pp. 139—154]。我们的算法实际上解决了在区间巢有向图中计算最大基数“弱独立集”的更一般的问题，这可能是独立的兴趣。进一步，我们给出了计算固有区间图和二部置换图的最大基数唯一限制匹配的线性时间算法。
A matching $M$ in a graph $G$ is said to be uniquely restricted if there is no other matching in $G$ that matches the same set of vertices as $M$. We describe a polynomial-time algorithm to compute a maximum cardinality uniquely restricted matching in an interval graph, thereby answering a question of Golumbic, Hirst, and Lewenstein [Algorithmica, 31 (2001), pp. 139--154]. Our algorithm actually solves the more general problem of computing a maximum cardinality “weak independent set” in an interval nest digraph, which may be of independent interest. Further, we give linear-time algorithms for computing maximum cardinality uniquely restricted matchings in proper interval graphs and bipartite permutation graphs.