AN EFFICIENT ALGORITHM FOR THE MINIMUM-RANGE IDEAL PROBLEM

スポンサーリンク

概要

• 論文の詳細を見る

• Suppose we are given a partially ordered set, a real-valued weight associated with each element and a positive integer k. We consider the problem which asks to find an ideal of size k of the partially ordered set such that the range of the weights is minimum. We call this problem the minimum-range ideal problem. This paper shows a new and fast O(n log n+m) algorithm for this problem, where n is the number of elements and m is the smallest number of arcs to represent the partially ordered set. It is also proved that this problem has an Ω(n log n+m) lower bound. This means that the algorithm presented in this paper is optimal.

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

著者

• Nemoto Toshio

  Department Of Science And Technology Graduate School Of Meiji University

• Nemoto T

  Bunkyo University

• Nemoto Toshio

  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
• AN EFFICIENT ALGORITHM FOR THE MINIMUM-RANGE IDEAL PROBLEM

スポンサーリンク