有向パスグラフの最大連結支配集合分割
スポンサーリンク
概要
- 論文の詳細を見る
本稿では,グラフの最大連結支配集合分割問題について考察する.以下では,有向パスグラフの部分クラスに対してこの問題が多項式時間で解けることを示す.有向パスグラフとは,有向木上の有向パスによってモデル化される交差グラフであり,区間グラフのひとつの拡張になっている.本稿で考える有向パスグラフの部分クラスは,有向木中の入次数2以上のノードが高々ひとつであるという制約が課せられたクラスである.
- 2008-05-20
著者
関連論文
- 分散ハッシュテーブル型P2Pシステムにおけるブルームフィルタを用いた高速連言検索手法の評価(2006年並列/分散/協調処理に関する『高知』サマー・ワークショップ(SWoPP高知2006)
- 組合せオｰクションの勝者決定問題に対する分枝限定解法の機能並列化手法
- 組合せオークションの勝者決定問題に対する分枝限定解法の機能並列化手法(性能評価環境と応用)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- 無線センサネットワークを利用した位置測位システムの構築(性能評価環境と応用)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- 有向パスグラフの最大連結支配集合分割