MATROID INTERSECTION WITH PRIORITY CONSTRAINTS

スポンサーリンク

概要

• 論文の詳細を見る

• In this paper, we consider the following variant of the matroid intersection problem. We are given two matroids M_1, M_2 on the same ground set E and a subset A of E. Our goal is to find a common independent set I of M_1, M_2 such that |I∩A| is maximum among all common independent sets of M_1, M_2 and such that (secondly) |I| is maximum among all common independent sets of M_1, M_2 satisfying the first condition. This problem is a matroid-generalization of the simplest case of the rank-maximal matching problem introduced by Irving, Kavitha, Mehlhorn, Michail and Paluch (2006). In this paper, we extend the "combinatorial" algorithm of Irving et at. for the rank-maximal matching problem to our problem by using a Dulmage-Mendelsohn type decomposition for the matroid intersection problem.

• 2013-03-00

著者

• Kamiyama Naoyuki

  Kyushu University

関連論文

• NETAL : HIGH-PERFORMANCE IMPLEMENTATION OF NETWORK ANALYSIS LIBRARY CONSIDERING COMPUTER MEMORY HIERARCHY(SCOPE (Seminar on Computation and OPtimization for new Extensions))
• MATROID INTERSECTION WITH PRIORITY CONSTRAINTS

スポンサーリンク