極大平面グラフにおける完全独立全域木について

スポンサーリンク

概要

• 論文の詳細を見る

• T_1, T_2, …, T_kをグラフGの全域木とする。Gの任意の二頂点u, vに対して、T_1, T_2, …, T_kにおけるuからvへのパスが互いに辺素かつ内素であるときに、T_1, T_2, …, T_kは完全独立であるという。本論文では、(外三角を除く)三角形内部に頂点を持たない、頂点数4以上の極大平面グラフには、2つの完全独立全域木が存在することを証明する。また, 与えられたグラフにおける2つの完全独立全域木を見つける問題はNP困難であることも証明する。

• 社団法人電子情報通信学会の論文
• 2001-01-15

著者

• 蓮沼 徹

  電子情報通信学会:電気通信大学電気通信学部情報工学科

• 蓮沼 徹

  電気通信大学 情報工学科

関連論文

• 少ない辺で上手につなごう(学生/教養のページ)
• 極大平面グラフにおける完全独立全域木について
• ラインダイグラフの底グラフにおける完全独立全域木 (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)
• ラインダイグラフの底グラフにおける完全独立全域木

スポンサーリンク