THE MINIMUM-WEIGHT IDEAL PROBLEM FOR SIGNED POSETS

スポンサーリンク

概要

• 論文の詳細を見る

• The concept of signed poset has recently been introduced by V. Reiner as a generalization of that, of ordinary poset (partially ordered set). We consider the problem of finding a minimum-weight ideal of a signed poset. We show a representation theorem that there exists a bijection between the set of all the ideals of a signed poset and the set of all the "reduced ideals" (defined here) of the associated ordinary poset, which was earlier proved by S. D. Fischer in his Ph.D. thesis. It follows from this representation theorem that the minimum-weight ideal problem for a signed poset can be reduced to a problem of finding a minimum-weight (reduced) ideal of the associated ordinary poset and hence to a minimum-cut problem. We also consider the case when the weight of an ideal is defined in terms of two weight functions. The problem is also reduced to a minimum-cut problem by the same reduction technique as above. Furthermore, the relationship between the minimum-weight ideal problem and a certain bisubmodular function minimization problem is revealed.

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

著者

• Ando Kazutoshi

  Institute Of Policy And Planning Scicnces University Of Tsukuba

• Ando Kazutoshi

  Institute Of Policy And Planning Sciences University Of Tsukuba

• Ando Kazutoshi

  University Of Tsukuba

• NEMOTO Toshio

  Department of Electronics and Communications, School of Science and Technology, Meiji University

• Fujishige Satoru

  Institute of Policy and Planning Sciences University of Tsukuba

• Nemoto Toshio

  Department Of Science And Technology Graduate School Of Meiji University

• Nemoto Toshio

  Department Of Business And Information Faculty Of Information And Communication Bunkyo University

関連論文

• Continuous Output Beam Steering in Vertical-Cavity Surface-Emitting Lasers with Two p-Type Electrodes by Controlling Injection Current Profile
• Improvement of DC Characteristics in AlGaN/GaN Heterojunction Field-Effect Transistors Employing AlN Spacer Layer
• Temperature Characteristics AlGaN/GaN Heterojunction Field Effect Transistors
• Advantages of AlN/GaN Metal Insulator Semiconductor Field Effect Transistor using Wet Chemical Etching With Hot Phosphoric Acid : Semiconductors
• AlGaN/GaN Heterojunction High Electron Mobility Transistors Using Ga-Polarity Crystal Growth by Plasma-Assisted Molecular Beam Epitaxy
• THE MINIMUM-WEIGHT IDEAL PROBLEM FOR SIGNED POSETS
• BALANCED BISUBMODULAR SYSTEMS AND BIDIRECTED FLOWS
• A GREEDY ALGORITHM FOR MINIMIZING A SEPARABLE CONVEX FUNCTION OVER A FINITE JUMP SYSTEM
• A GREEDY ALGORITHM FOR MINIMIZING A SEPARABLE CONVEX FUNCTION OVER AN INTEGRAL BISUBMODULAR POLYHEDRON
• AN EFFICIENT ALGORITHM FOR THE MINIMUM-RANGE IDEAL PROBLEM
• An Almost-Linear-Time Algorithm for Solving the Graph-Realization Problem (Graphs and Combinatorics III)
• A DUAL ALGORITHM FOR FINDING THE MINIMUM-NORM POINT IN A POLYTOPE
• A DUAL ALGORITHM FOR FINDING A NEAREST PAIR OF POINTS IN TWO POLYTOPES
• AN EFFICIENT COST SCALING ALGORITHM FOR THE INDEPENDENT ASSIGNMENT PROBLEM

もっと見る 閉じる

スポンサーリンク