AN ALGORITHM FOR FINDING AN OPTIMAL INDEPENDENT LINKAGE

スポンサーリンク

概要

• 論文の詳細を見る

• This paper considers the weighted independent linkage problem which is a natural extension of the independent assignment problem recently treated by M. Iri and N. Tomizawa. Given a directed graph with two specified vertex subsets V_1 and V_2 on which matroidal structures are defined respectively, an independent linkage is a set of pairwise-arc-disjoint paths from V_1 to V_2 such that the set of the initial vertices (resp. terminal vertices) of those paths is an independent set on V_1 ・(resp. V_2). The problem is to find an optimal independent linkage, i.e., a maximum independent linkage having the smallest total weight among all maximum independent linkages, where a weight is given to each arc. We present an algorithm for finding an optimal independent linkage.

• 社団法人日本オペレーションズ・リサーチ学会の論文

著者

• Fujishige Satoru

  Department Of Mathematical Engineering And Instrumentation Physics Faculty Of Engineering University

関連論文

• AN ALGORITHM FOR FINDING AN OPTIMAL INDEPENDENT LINKAGE
• A PRIMAL APPROACH TO THE INDEPENDENT ASSIGNMENT PROBLEM

スポンサーリンク