효율적인 D-클래스 계산을 위한 알고리즘

• 영문명: Algorithm for Efficient D-Class Computation
• 발행기관: 한국IT서비스학회
• 저자명: 한재일(Jae-Il Han)
• 간행물 정보: 『한국IT서비스학회지』한국IT서비스학회지 제6권 제1호, 151~158쪽, 전체 8쪽
• 주제분류: 경제경영 > 경영학
• 파일형태: PDF
• 발행일자: 2007.04.30

영문 초록

  D-class computation requires multiplication of three Boolean matrices for each of all possible triples of n×n Boolean matrices and search for equivalent n×n Boolean matrices according to a specific equivalence relation. It is easy to see that even multiplying all n×n Boolean matrices with themselves shows exponential time complexity and D-Class computation was left an unsolved problem due to its computational complexity. The vector-based multiplication theory shows that the multiplication of three Boolean matrices for each of all possible triples of n×n Boolean matrices can be done much more efficiently. However, D-Class computation requires computation of equivalent classes in addition to the efficient multiplication. The paper discusses a theory and an algorithm for efficient D-class computation, and shows execution results of the algorithm.

목차

Abstract
1. 서론
2. 관련 연구 및 문제점
3. 용어 및 기호 정의
4. D-클래스 계산 알고리즘
5. D-클래스 계산 알고리즘 및 실행결과
6. 결론 및 향후 연구방향
참고문헌
저자소개

키워드

D-Class Boolean Matrix Algorithm Computational Complexity NP-Complete