The Popular Matching and Condensation Problems under Matroid Constraints
The Popular Matching and Condensation Problems under Matroid Constraints
复制标题
拟阵约束下的流行匹配和凝聚问题
DOI：
10.1007/978-3-319-12691-3_53
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Naoyuki Kamiyama
中科院分区：
文献类型：
--
作者：
Naonori Kakimura;Yusuke Kobayashi and Ken-ichi Kawarabayashi;澄田範奈，垣村尚徳，牧野和久;澄田範奈，垣村尚徳，牧野和久;Naonori Kakimura and Ken-ichi Kawarabayashi;Naoyuki Kamiyama
在本文中，我们首先考虑由Abraham，欧文，Kavitha和Mehlhorn提出的流行的匹配问题（无结）的拟阵推广，并给出了这个问题的多项式时间算法。在本文的后半部分，我们考虑的问题，通过删除最小数量的申请人，使它有一个受欢迎的匹配下拟阵约束的流行匹配问题（没有领带）的一个给定的实例。这个问题是一个拟阵推广流行的凝聚问题提出的吴，林，王，和超。利用前半部分的结果，我们给出了该问题的一个多项式时间算法。
In this paper, we first consider a matroid generalization of the popular matching problem (without ties) introduced by Abraham, Irving, Kavitha, and Mehlhorn, and give a polynomial-time algorithm for this problem. In the second half of this paper, we consider the problem of transforming a given instance of the popular matching problem (without ties) by deleting a minimum number of applicants so that it has a popular matching under matroid constraints. This problem is a matroid generalization of the popular condensation problem proposed by Wu, Lin, Wang, and Chao. By using the results in the first half, we give a polynomial-time algorithm for this problem.