整列問題のネットワークフローモデルによる解釈とその拡張

• Item type: Trans(1)
• 公開日: 1999-12-15
• タイトル: 整列問題のネットワークフローモデルによる解釈とその拡張
• タイトル / 言語: en
• タイトル: Interpretation of Sorting with Network-flow Models and Extensions
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 事例報告
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 東京農工大学（現 株式会社構造計画研究所）
• 著者所属: 東京農工大学
• 著者所属(英): en
• 著者所属(英): Tokyo A&T University(KOZO KEIKAKU ENGINEERING Inc.)
• 著者所属(英): en
• 著者所属(英): Tokyo A&T University
• 著者名: 萩原, 斉; 中森, 眞理雄
• 著者名(英): Hitoshi, Hagiwara; Mario, Nakamori
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 線形計画問題を 情報科学の基本的問題の記述に適用した事例報告である.具体的には 整列問題を線形計画問題として記述した例を示し 変数や双対問題の意味のさまざまな角度からの解釈を試みる.さらに 線形計画問題として記述された整列問題を割り当て問題として記述し それを実現する回路を示す.この回路がO(nlog2 n)個の素子で実現できることを示す.次に この手法を一般に困難とされている問題に拡張する方法を試みる.具体的には グラフにおいてクリークが存在するか否かを判定する問題を取り上げ 双線形計画問題として記述した例を示す.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In the present paper, we show examples of applying linear programming problem to basic problems of computer sience. For instance, it is shown that the problem of sorting data is described as a linear progamming problem, and the variables and the constraints of the primal and the dual problems are interpreted from various of view. Further, the sort problem is described as an assignment problem and an electric circuit. This circuit is made of O(nlog2 n)electrical elements. We extend this method to a problem that is generally regarded as hard problems. As an example, the clique problem is described as a bilinear programming problem.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464803
• 書誌情報: 情報処理学会論文誌数理モデル化と応用（TOM）; 巻 40, 号 SIG09(TOM2), p. 150-159, 発行日 1999-12-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7780
• 出版者 / 言語: ja
• 出版者: 情報処理学会