A Method to Reduce the Size or Matrices Which Represent the Minimum Cover Problem

IPSJ

Bibliographic Information

Other Title
  • 最小被覆問題を表現する行列のサイズの縮小法

Search this article

Description

代表的なNP完全問題の一つに最小被覆問題がある.最小被覆問題は行列T=(t_<ij>),t_<ij>∈{1,0}から,できるだけ少ない数の行ベクトルを選んで和をとるとき,その要素がすべて1以上となるようにする問題として表現できる.本稿では,行縮小作用素Rと列縮小作用素Cを定義し,これらを行列Tに繰り返し作用させることにより,最小被覆問題の意味でTと等価でサイズが小さい行列Tを決定論的に得る方法を提出する.また,可能な限り縮小化して得られた行列のサイズはRとCを作用させる順番に依存せず一定となることを証明する.最後に,ISCAS'85ベンチマーク回路より生成された故障表に本縮小法を適用し,その有効性を示す.

Journal

  • 全国大会講演論文集

    全国大会講演論文集 第53回 (ソフトウェア科学・工学), 187-188, 1996-09-04

    情報処理学会

Details 詳細情報について

Report a problem

Back to top