自己診断システムにおけるネットワーク構造と計算複雑さ

阿江 忠  大崎 重義  

誌名
電子情報通信学会論文誌 D   Vol.J62-D   No.2   pp.126-132
発行日: 1979/02/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: 
キーワード: 


本文: PDF(510.2KB)>>
論文を購入




あらまし: 
ラベルつき有向グラフで表されるシステムの自己診断法については,Preparata,et al.以来いろいろ議論されてきている.現在までに判明している問題点の一つは,故障ユニットの集合を求めるという基本的問題が一般には完全となることであり,このため,一般には効率のよいアルゴリズムの存在が期待できない.そこで,従来は,故障の性質に制限をつけたり,診断の方法を変えることで多項式時間アルゴリズムを得てきた.本論文では,従来と異なり,ネットワーク構造からみた診断の計算複雑さを論じ,(1)アサイクリック(acyclic)でも問題の複雑さは同じこと,(2)制限されたネットワーク構造では多項式時間アルゴリズムが存在することを示す.(2)の具体的な結果としては,直並列ネットワーク及びその拡張であるDチャート状ネットワークではOn2)のアルゴリズムの存在することが示される.