맞춤기술찾기

홈으로 가기
맞춤기술찾기
이전대상기술
프린트하기

이전대상기술

인접행렬을 이용하여 최소 길이의 폐구간을 이루는노드들을 검출하는 프로그램이 저장된 매체

  • 기술번호 : KST2014011363
  • 담당센터 : 서울서부기술혁신센터
  • 전화번호 : 02-6124-6930
상담신청 PDF 받기
요약, Int. CL, CPC, 출원번호/일자, 출원인, 등록번호/일자, 공개번호/일자, 공고번호/일자, 국제출원번호/일자, 국제공개번호/일자, 우선권정보, 법적상태, 심사진행상태, 심판사항, 구분, 원출원번호/일자, 관련 출원번호, 기술이전 희망, 심사청구여부/일자, 심사청구항수의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 서지정보 표입니다.
요약 본 발명은 인접행렬을 이용하여 각 노드 간의 연결 관계를 파악하는 기법에 관한 것으로, 구체적으로는, 최소 길이의 폐구간을 이루는 노드들을 찾는 기법 및 그 기법에 따른 프로그램을 제안하는 것이다. 본 발명에 따른 기법은, 컴퓨터로 하여금 인접 행렬에 대한 거듭 제곱을 하여 가장 먼 원소를 찾고, 이후 거듭 제곱의 횟수를 감소시키며 SSSR에 속하는 원소를 찾도록 하는 방법을 제안한다. 보다 구체적으로, 본 발명은 i) 찾으려는 최소 링의 길이에 상응하는 횟수만큼 인접행렬을 거듭제곱하여 n차 행렬을 생성하고, ii) n차 행렬을 이용하여 시작점에서 가장 먼 원소를 파악하며, iii) n차 행렬의 지수를 순차적으로 감소시키며 시작점과 가장 먼 원소 사이에 있는 원소들을 파악하는 기능을 실현하기 위한 프로그램을 제공한다. 본 발명을 이용하는 경우, 빠른 속도로 정확하게 SSSR을 찾을 수 있는 장점이 있다. 인접행렬, 최소 링, SSSR, 링 인식, ring perception
Int. CL G06F 17/10 (2006.01)
CPC G06F 17/16(2013.01)
출원번호/일자 1020080009211 (2008.01.29)
출원인 연세대학교 산학협력단, 사단법인 분자설계연구소, 숭실대학교산학협력단
등록번호/일자 10-0920966-0000 (2009.10.01)
공개번호/일자 10-2009-0083198 (2009.08.03) 문서열기
공고번호/일자 (20091009) 문서열기
국제출원번호/일자
국제공개번호/일자
우선권정보
법적상태 소멸
심사진행상태 수리
심판사항
구분 신규
원출원번호/일자
관련 출원번호
심사청구여부/일자 Y (2008.01.29)
심사청구항수 16

출원인

번호, 이름, 국적, 주소의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 인명정보 - 출원인 표입니다.
번호 이름 국적 주소
1 연세대학교 산학협력단 대한민국 서울특별시 서대문구
2 사단법인 분자설계연구소 대한민국 서울특별시 서대문구
3 숭실대학교산학협력단 대한민국 서울특별시 동작구

발명자

번호, 이름, 국적, 주소의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 인명정보 - 발명자 표입니다.
번호 이름 국적 주소
1 노경태 대한민국 서울 강남구
2 이창준 대한민국 서울 광진구
3 조광휘 대한민국 서울 동작구
4 박재성 대한민국 인천 서구
5 이성광 대한민국 서울 동작구

대리인

번호, 이름, 국적, 주소의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 인명정보 - 대리인 표입니다.
번호 이름 국적 주소
1 윤항식 대한민국 서울특별시 강남구 역삼로 *길 **, 신관 *층~*층, **층(역삼동, 광성빌딩)(특허법인다나)
2 진희동 대한민국 서울특별시 강남구 역삼로 *길 **, 신관 *층~*층, **층(역삼동, 광성빌딩)(특허법인다나)
3 연무식 대한민국 서울(특허법인 퇴사후 사무소변경 미신고)

최종권리자

번호, 이름, 국적, 주소의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 인명정보 - 최종권리자 표입니다.
번호 이름 국적 주소
1 연세대학교 산학협력단 대한민국 서울특별시 서대문구
2 사단법인 분자설계연구소 대한민국 서울특별시 서대문구
3 숭실대학교산학협력단 대한민국 서울특별시 동작구
번호, 서류명, 접수/발송일자, 처리상태, 접수/발송일자의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 행정처리 표입니다.
번호 서류명 접수/발송일자 처리상태 접수/발송번호
1 [특허출원]특허출원서
[Patent Application] Patent Application		 2008.01.29 수리 (Accepted) 1-1-2008-0075882-57
2 보정요구서
Request for Amendment		 2008.02.01 발송처리완료 (Completion of Transmission) 1-5-2008-0016627-08
3 [출원서등 보정]보정서
[Amendment to Patent Application, etc.] Amendment		 2008.02.13 수리 (Accepted) 1-1-2008-0108322-75
4 선행기술조사의뢰서
Request for Prior Art Search		 2008.09.08 수리 (Accepted) 9-1-9999-9999999-89
5 선행기술조사보고서
Report of Prior Art Search		 2008.10.15 수리 (Accepted) 9-1-2008-0068269-78
6 등록결정서
Decision to grant		 2009.07.31 발송처리완료 (Completion of Transmission) 9-5-2009-0320483-16
7 출원인정보변경(경정)신고서
Notification of change of applicant's information		 2011.12.15 수리 (Accepted) 4-1-2011-5252006-10
8 출원인정보변경(경정)신고서
Notification of change of applicant's information		 2013.04.24 수리 (Accepted) 4-1-2013-5062749-37
9 출원인정보변경(경정)신고서
Notification of change of applicant's information		 2013.06.24 수리 (Accepted) 4-1-2013-5088566-87
10 출원인정보변경(경정)신고서
Notification of change of applicant's information		 2014.09.25 수리 (Accepted) 4-1-2014-5114224-78
11 출원인정보변경(경정)신고서
Notification of change of applicant's information		 2015.02.12 수리 (Accepted) 4-1-2015-0009099-11
12 출원인정보변경(경정)신고서
Notification of change of applicant's information		 2016.08.04 수리 (Accepted) 4-1-2016-5110636-51
번호, 청구항의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 청구항 표입니다.
번호 청구항
1 1
컴퓨터에 네트워크 상에 위치하는 노드(node)들의 연결 관계를 나타내는 인접행렬을 획득하는 제1 기능; 소정의 최소 길이의 폐구간을 이루는 노드들을 검출하기 위하여, 상기 최소 길이에 상응하는 최대 지수(exponent)만큼 상기 인접행렬을 거듭 제곱하여 최대지수 경로행렬을 산출하는 제2 기능; 상기 최대지수 경로행렬 및 상기 최대지수 경로행렬에 비해 낮은 지수를 갖는 적어도 하나의 경로행렬을 이용하여 소정의 제1 노드로부터 가장 이격된 제2 노드를 탐색하는 제3 기능; 상기 최대지수 경로행렬의 지수를 순차적으로 감소시켜 산출한 적어도 하나의 경로행렬을 이용하여, 상기 제1 노드에서 상기 제2 노드 방향으로 상기 제1 노드 및 상기 제2 노드 사이에 위치하는 적어도 하나의 노드를 순차적으로 검출하는 제4 기능; 및 상기 제1 노드, 상기 제2 노드 및 상기 제4 기능에 의해 검출된 노드를, 최소 길이의 폐구간을 이루는 하나의 노드 집합으로 그룹화(grouping)하는 제5 기능 을 실행시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 매체
2 2
제1항에 있어서, 상기 인접행렬의 모서리(edge) 및 꼭지점(vertex)의 개수를 이용하여, 상기 인접행렬에서 검출 가능한 최소 길이의 폐구간의 개수를 산출하는 제6 기능 을 더 실행시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 매체
3 3
제2항에 있어서, 상기 제6 기능에 의해 그룹화된 노드 집합의 개수가 상기 제6 기능에 의해 산출된 폐구간의 개수와 동일해질 때까지, 상기 최소 길이를 순차적으로 증가시키며 상기 제2 기능 내지 제5 기능을 반복 수행하는 제7 기능 을 더 실행시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 매체
4 4
제1항에 있어서, 상기 최소 길이가 짝수인 경우, 상기 최대 지수(m) 및 상기 최소 길이(n)는 에 의하고, 상기 최소 길이가 홀수인 경우, 상기 최대 지수(m) 및 상기 최소 길이(n)는 에 의하는 것을 특징으로 하는 프로그램을 기록한 컴퓨터로 읽을 수 있는 매체
5 5
제1항에 있어서, 상기 최소 길이가 짝수인 경우, 상기 제3 기능은, 상기 최대지수 경로행렬에 포함된 성분(element) 및 상기 최대지수 경로행렬에 비해 낮은 지수를 갖는 경로행렬 전부를 비교하여, 상기 낮은 지수의 경로행렬에서 ‘0’ 성분을 가지며, 상기 최대지수 경로행렬에서 ‘2’ 이상의 성분을 갖는 노드를 탐색하는 기능인 것을 특징으로 하는 프로그램을 기록한 컴퓨터로 읽을 수 있는 매체
6 6
제1항에 있어서, 상기 최소 길이가 홀수인 경우, 상기 제3 기능은, 상기 최대지수 경로행렬에 포함된 성분(element) 및 상기 최대지수 경로행렬에 비해 낮은 지수를 갖는 경로행렬 전부를 비교하여, 상기 낮은 지수의 경로행렬에서 ‘0’ 성분을 가지며, 상기 최대지수 경로행렬에 비해 지수가 ‘1’ 만큼 낮은 경로행렬과 상기 최대지수 경로행렬에서 ‘1’ 이상의 성분을 갖는 노드를 탐색하는 기능인 것을 특징으로 하는 프로그램을 기록한 컴퓨터로 읽을 수 있는 매체
7 7
제1항에 있어서, 상기 제4 기능은, 상기 최소 길이가 짝수인 경우, 상기 최대지수 경로행렬의 지수를 순차적으로 감소시키기 위한 카운터를 초기화시키는 제8 기능; 상기 최대지수 경로행렬보다 상기 카운터만큼 차수가 감소한 경로행렬을 산출하는 제9 기능; 상기 제9 기능에 의해 산출된 경로행렬을 이용하여, 상기 제1 노드로부터 상기 카운터에 상응하는 길이만큼 이격된 노드를 검출하는 제10 기능; 및 상기 제1 노드 및 상기 제2 노드 사이에 위치하는 노드가 전부 검출될 때까지, 상기 카운터를 증가시키며 상기 제9 기능 및 상기 제10 기능을 반복 수행하는 제11 기능을 포함하는 것을 특징으로 하는 프로그램을 기록한 컴퓨터로 읽을 수 있는 매체
8 8
제1항에 있어서, 상기 제4 기능은, 상기 최소 길이가 홀수인 경우, 상기 최대지수 경로행렬에 비해 지수가 ‘1’ 만큼 감소한 중간 경로행렬을 이용하여, 상기 제1 노드로부터 제1 방향으로 거리가 ‘1’ 만큼 이격된 제3 노드를 검출하는 제12 기능; 상기 중간 경로행렬의 지수를 순차적으로 감소시키기 위한 카운터를 초기화시키는 제13 기능; 상기 중간 경로행렬에 비해 차수가 상기 카운터만큼 감소한 경로행렬을 산출하는 제14 기능; 상기 제14 기능에 의해 산출된 경로행렬을 이용하여, 상기 제1 노드로부터 제2 방향으로 상기 카운터에 상응하는 길이만큼 이격된 노드 및 상기 제3 노드로부터 제1 방향으로 상기 카운터에 상응하는 길이만큼 이격된 노드를 검출하는 제15 기능; 및 상기 제1 노드 및 상기 제2 노드 사이에 위치하는 노드가 전부 검출될 때까지, 상기 카운터를 증가시키며 상기 제14 기능 및 상기 제15 기능을 반복 수행하는 제16 기능을 포함하는 것을 특징으로 하는 프로그램을 기록한 컴퓨터로 읽을 수 있는 매체
9 9
제1항에 있어서 상기 제5 기능은, 이미 그룹화된 노드 집합이 존재하는 경우, 새롭게 그룹화된 노드 집합이 이미 그룹화된 노드 집합의 노드들을 전부 포함하는지 여부를 검사하는 제17 기능을 더 포함하는 것을 특징으로 하는 프로그램을 기록한 컴퓨터로 읽을 수 있는 매체
10 10
제9항에 있어서 상기 제17 기능은, 배타합(exclusive-OR) 연산에 의해 수행되는 것을 특징으로 하는 프로그램을 기록한 컴퓨터로 읽을 수 있는 매체
11 11
제1항에 있어서 상기 인접행렬에 포함된 개방된 비환식 노드(open acyclic node)를 제거하는 제18 기능을 더 수행하는 프로그램을 기록한 컴퓨터로 읽을 수 있는 매체
12 12
제1항에 있어서 상기 인접 행렬은 분자에 포함된 원자들의 연결 관계를 나타내는 것을 특징으로 하는 프로그램을 기록한 컴퓨터로 읽을 수 있는 매체
13 13
컴퓨터에 네트워크 상에 위치하는 노드(node)들의 연결 관계를 나타내는 인접행렬을 획득하는 제1 단계; 상기 인접행렬의 모서리(edge) 및 꼭지점(vertex)의 개수를 이용하여, 상기 인접행렬에서 검출 가능한 최소 길이의 폐구간의 개수를 산출하는 제2 단계; 상기 폐구간의 길이를 순차적으로 증가시키기 위한 제1 카운터를 초기화 시키는 제3 단계; 상기 제1 카운터에 상응하는 길이의 폐구간을 이루는 노드들을 검출하기 위하여, 상기 제1 카운터에 상응하는 최대 지수(exponent)만큼 상기 인접행렬을 거듭 제곱하여 최대지수 경로행렬을 산출하는 제4 단계; 상기 최대지수 경로행렬 및 상기 최대지수 경로행렬에 비해 낮은 지수를 갖는 적어도 하나의 경로행렬을 이용하여 소정의 제1 노드로부터 가장 이격된 제2 노드를 탐색하는 제5 단계; 상기 제1 노드 및 제2 노드 사이에 위치하는 노드를 검출하기 위한 제2 카운터를 초기화시키는 제6 단계; 상기 최대지수 경로행렬에 비해 지수가 상기 제2 카운터만큼 감소하는 중간 경로행렬을 산출하는 제7 단계; 상기 중간 경로행렬을 이용하여, 상기 제1 노드에서 상기 제2 노드 방향으로 상기 제1 노드에서 상기 제2 카운터에 상응하는 거리만큼 이격된 적어도 하나의 노드를 순차적으로 검출하는 제8 단계; 상기 제1 노드 및 상기 제2 노드 사이에 위치하는 노드가 모두 검출될 때까지, 상기 제2 카운터를 증가시키면서 상기 제7 단계 및 상기 제8 단계를 반복 수행하는 제9 단계; 상기 제1 노드, 상기 제2 노드 및 상기 검출된 노드를, 최소 길이의 폐구간을 이루는 하나의 노드 집합으로 그룹화(grouping)하는 제10 단계; 상기 제10 단계에 의해 그룹화된 노드 집합의 개수가 상기 제2 단계에 의한 검출 가능한 최소 길이의 폐구간의 개수와 일치할 때까지, 상기 제1 카운터를 증가시키면서 상기 제4 단계 내지 상기 제10 단계를 반복 수행하는 제11 단계 를 실행시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 매체
14 14
제13항에 있어서, 상기 제1 카운터가 짝수인 경우, 상기 최대 지수(m) 및 상기 제1 카운터(n)는 에 의하고, 상기 제1 카운터가 홀수인 경우, 상기 최대 지수(m) 및 상기 제1 카운터(n)는 에 의하는 것을 특징으로 하는 프로그램을 기록한 컴퓨터로 읽을 수 있는 매체
15 15
제13항에 있어서 상기 인접행렬은 개방된 비환식 노드(open acyclic node)가 제거된 행렬인 것을 특징으로 하는 프로그램을 기록한 컴퓨터로 읽을 수 있는 매체
16 16
제13항에 있어서 상기 인접행렬에 포함된 성분은 각 노드 간에 경로가 존재하는지 여부를 나타내는 것을 특징으로 하는 프로그램을 기록한 컴퓨터로 읽을 수 있는 매체
지정국 정보가 없습니다
패밀리정보가 없습니다
국가 R&D 정보가 없습니다.