A LINEAR TIME ALGORITHM FOR THE GENERALIZED STABLE SET PROBLEM ON TRIANGULATED BIDIRECTED GRAPHS

スポンサーリンク

概要

• 論文の詳細を見る

• The generalized stable set problem is an extension of the maximum weight stable set problem for undirected graphs to bidirected graphs. This paper shows that the problem on triangulated bidirected graphs is solvable in linear time. We also propose an exact branch and bound algorithm for the general problem by applying the linear time algorithm.

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

著者

• 田村 明久

  慶應義塾大学

• Tamura Akihisa

  Kyoto University

• Nakamura Daishin

  University of Electro-Communications

• Nakamura D

  Hokkaido Univ. Hokkaido Jpn

関連論文

• 1-F-10 Existence of sports schedules with multiple venues
• パーフェクト双向グラフ(グラフ・ネットワーク(3))
• On the Local Face Structure of 0-1 Polytopes Related to a Class of Combinatorial Optimizaiton Problems
• Adjacency of the Best and Second Best Valued Solutions in Combinatorial Optimization Problems
• Algorithms for Finding a Kth Best Valued Assignment
• A Recursive Algorithm for a Class of Convex Min-Max Problems
• ON GROTSCHEL-LOVASZ-SCHRIJVER'S RELAXATION OF STABLE SET POLYTOPES
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• A LINEAR TIME ALGORITHM FOR THE GENERALIZED STABLE SET PROBLEM ON TRIANGULATED BIDIRECTED GRAPHS
• 確率モデルにおける最適化研究部会終了報告(ペーパーフェア)
• 制限付き安定部屋割問題とミニマックス安定部屋割問題(組合せ・グラフ・ネットワーク)
• The Rooted Tree Embedding Problem
• A property of the divorce digraph for a stable marriage
• マッチングモデルと離散凸解析を用いたその拡張 : アルゴリズムの観点から(セッション2)
• マッチングモデル(モデリング-最適化モデリング-)
• 第22回FMESシンポジウム「デジタル・エンジニアリングと経営工学」(情報の窓)
• A NEW CHARACTERIZATION OF M^〓-CONVEX SET FUNCTIONS BY SUBSTITUTABILITY
• 安定結婚からサプライチェーンネットワークの安定性へ(離散凸解析)
• 2-B-4 サプライチェーンネットワークの安定性(離散最適化(5))

もっと見る 閉じる

スポンサーリンク