最大リーフ全域木問題の上界値計算について

• Item type: SIG Technical Reports(1)
• 公開日: 1998-09-16
• タイトル: 最大リーフ全域木問題の上界値計算について
• タイトル / 言語: en
• タイトル: On Upper Bounding Computaions for the Maximum - Leaf Spanning Tree Problem
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 神戸商科大学管理科学科
• 著者所属(英): en
• 著者所属(英): Department of Management Science Kobe University of Commerce
• 著者名: 藤江, 哲也
• 著者名(英): Tetsuya, Fujie
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 最大リーフ全域木問題とは，連結無向グラフGの全域木の中で，リーフ（次数1の頂点）数が最大のものを求める問題である．この問題はNP?困難であり，いくつかの近似解法，すなわち下界値計算が提案されている．これに対し，本稿では，上界値計算に関連した議論を行う．まず，この問題の0?1整数計画問題としての定式化を2通り与える．次に，各定式化について，定式化に用いた不等式が，実行可能解集合の凸包として定義される多面体の極大面を定める必要十分条件を与える．最後に，緩和問題について触れる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Given an undirected graph G, the Maximum-Leaf Spanning Tree Problem is to find a spanning tree in G, whose number of leaves (degree-1 vertices) is maximum. The problem is NP-hard, and several approximation algorithms, that is, lower bounding computations, are proposed. This paper concerns with upper bounding computations. First, we provide two kinds of O-1 integer programming formulations of the problem. Next, we give necessary and sufficient conditions that the constraints in each formulation define facets of a polytope which is defined as a convex hull of the set of feasible solutions. Finally, relaxation problems are considered.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1998, 号 78(1998-AL-064), p. 17-24, 発行日 1998-09-16
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会