문맥 자유 그래프 언어의 효과적인 연결성 문제의 복잡도 분석

여러가지 제약 조건하의 문맥 자유 그래프 언어상에서 우리는 연결성 문제들의 간결한 그래프 표현과 그에 대한 복잡도를 분석한다. 문맥 자유 그래프 문법인 SNLC 문법을 정의하고 그래프 생성시 확장 과정에서 필요한 많은 공간을 줄일 수 있는 축약방법을 소개한다. 그래프상의 연결성 문제의 효과적 해결책의 방법을 예증하고 축약 병렬 알고리즘을 구현하고 복잡도를 분석한다. 우리의 결과는 NETWORK, CAD, VLSI등의 공학 설계에 많은 도움이 될것이다.