검색 기능은 준비 중입니다.
검색 기능은 준비 중입니다.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Generation of Minimal Separating Sets of a Graph 그래프의 최소 분리 세트 생성

Jiro HAYAKAWA, Shuji TSUKIYAMA, Hiromu ARIYOSHI

  • 조회수

    0

  • 이것을 인용

요약 :

주어진 무방향 그래프의 경우 G[V,E] 및 정점 s and t, 로 표시되는 최소 st 분리 세트 Ec & Vc 요소를 삭제할 수 있는 최소 요소 집합(가장자리 및/또는 정점)입니다. G 사이의 모든 경로를 끊습니다. s and t어디로 Ec and Vc 각각 모서리와 꼭지점의 집합입니다. 본 논문에서는 모든 최소 st 분리 집합을 생성하는 문제를 고려하고 이 문제가 다음 방법으로 해결될 수 있음을 보여줍니다. O(μ(mt(n,n))) 시간, 여기서 m|E|, n|V|, μ는 최소 st 분리 세트의 수입니다. Gt(p,q)는 p개의 꼭짓점을 가진 뿌리나무에서 q개의 꼭짓점 쌍에 대한 q개의 가장 낮은 공통 조상을 찾는 데 필요한 시간입니다. 부터 t(n,n)는 O(n), 우리는 st 분리 세트당 선형 시간으로 모든 최소 st 분리를 생성할 수 있습니다. 그러나 가장 낮은 공통 조상을 찾는 선형 시간 알고리즘은 복잡하므로 적당한 크기의 그래프에는 효율적이지 않습니다. 그러므로 우리는 O(nㅏ (n))-최하위 공통 조상을 찾기 위한 시간 알고리즘, 그리고 모든 최소 st 분리 집합을 생성하는 알고리즘을 제안합니다. O(mnα(n)) st 분리 세트당 시간, 여기서 α(n)는 Ackermann 함수의 의사 역함수입니다.

발행
IEICE TRANSACTIONS on Fundamentals Vol.E82-A No.5 pp.775-783
발행일
1999/05/25
공개일
온라인 ISSN
DOI
원고의 종류
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
범주

작성자

키워드