Reconfiguration of maximum-weight b-matchings in a graph

Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

研究成果: Article査読

3 被引用数 (Scopus)


Consider a graph such that each vertex has a nonnegative integer capacity and each edge has a positive integer weight. Then, a b-matching in the graph is a multi-set of edges (represented by an integer vector on edges) such that the total number of edges incident to each vertex is at most the capacity of the vertex. In this paper, we study a reconfiguration variant for maximum-weight b-matchings: For two given maximum-weight b-matchings in a graph, we are asked to determine whether there exists a sequence of maximum-weight b-matchings in the graph between them, with subsequent b-matchings obtained by removing one edge and adding another. We show that this reconfiguration problem is solvable in polynomial time for instances with no integrality gap. Such instances include bipartite graphs with any capacity function on vertices, and 2-matchings in general graphs. Thus, our result implies that the reconfiguration problem for maximum-weight matchings can be solved in polynomial time for bipartite graphs.

ジャーナルJournal of Combinatorial Optimization
出版ステータスPublished - 2019 2月 15

ASJC Scopus subject areas

  • コンピュータ サイエンスの応用
  • 離散数学と組合せ数学
  • 制御と最適化
  • 計算理論と計算数学
  • 応用数学


「Reconfiguration of maximum-weight b-matchings in a graph」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。