首页    期刊浏览 2024年10月06日 星期日
登录注册

文章基本信息

  • 标题:A CHARACTERIZATION OF WEIGHTED POPULAR MATCHINGS UNDER MATROID CONSTRAINTS
  • 本地全文:下载
  • 作者:Naoyuki Kamiyama
  • 期刊名称:日本オペレーションズ・リサーチ学会論文誌
  • 印刷版ISSN:0453-4514
  • 电子版ISSN:2188-8299
  • 出版年度:2018
  • 卷号:61
  • 期号:1
  • 页码:2-17
  • DOI:10.15807/jorsj.61.2
  • 语种:English
  • 出版社:Japan Science and Technology Information Aggregator, Electronic
  • 摘要:

    The popular matching problem introduced by Abraham, Irving, Kavitha, and Mehlhorn is one of bipartite matching problems with one-sided preference lists. In this paper, we first propose a matroid generalization of the weighted variant of popular matchings introduced by Mestre. Then we give a characterization of weighted popular matchings in bipartite graphs with matroid constraints and one-sided preference lists containing no ties. This characterization is based on the characterization of weighted popular matchings proved by Mestre. Lastly we prove that we can decide whether a given matching is a weighted popular matching under matroid constraints in polynomial time by using our characterization.

  • 关键词:Discrete optimization;popular matching;matroid
国家哲学社会科学文献中心版权所有