制約のあるスパンニングツリー問題について

スポンサーリンク

概要

• 論文の詳細を見る

• Many probrems concerning network design are very important and considered to be diffdicult combinatorial problems to solve. In fact, most of them are known to be NP-complete. We define a new network design problem (and its subproblems), the sapanning caterpillar problem, that is, the problem to decide whether or not, for a graph G (with the degree at most d) given as input, there exists a spanning caterpillar in G. We show this problem is NP-complete even if d≦3. It is a trivial problem for d≦2 because a connected graph with the degree at most 2 is a cycle or a path. So our result is best for the degree constraint.

• 八戸工業大学の論文
• 1989-02-28

著者

• 大川 知

  八戸工業大学電気工学科

• 大川 知

  八戸工業大学

関連論文

• 帰納的に可算な言語の線形言語の小さいクラスによる特性化
• スパンニングキャタピラ問題について
• スパンニングツリーの端点数に関する補間定理の別証明
• 帰納的に可算な言語の補集合演算を用いた特徴付けについて
• 帰納的に可算な言語の同長線形文脈自由言語による特徴付けについて
• 制約のあるスパンニングツリー問題について

スポンサーリンク