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

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

A Polynomial Delay Algorithm for Enumerating 2-Edge-Connected Induced Subgraphs 2-에지 연결 유도 서브그래프를 열거하기 위한 다항식 지연 알고리즘

Taishu ITO, Yusuke SANO, Katsuhisa YAMANAKA, Takashi HIRAYAMA

  • 조회수

    0

  • 이것을 인용

요약 :

주어진 그래프의 연결된 유도 하위 그래프를 열거하는 문제는 고전적이며 잘 연구되었습니다. 연결된 유도 하위 그래프는 각 하위 그래프에 대해 일정한 시간에 열거될 수 있는 것으로 알려져 있습니다. 본 논문에서는 고도로 연결된 유도 하위 그래프에 중점을 둡니다. 그래프에서 연결성의 가장 중요한 개념은 정점 연결성(Vertex Connectivity)입니다. 정점 연결의 경우 다음과 같은 일부 열거 문제 설정 및 열거 알고리즘이 제안되었습니다. k- 꼭지점 연결 스패닝 하위 그래프. 본 논문에서는 그래프 연결성의 또 다른 주요 개념인 에지 연결성에 중점을 둡니다. 이는 도로망에서 대피 경로를 찾는 문제에서 비롯되었습니다. 대피 경로에서는 에지 연결성이 중요합니다. 에지 연결성이 높은 하위 그래프가 두 정점 사이의 여러 경로를 보장하기 때문입니다. 본 논문에서는 주어진 그래프의 2-에지 연결 유도 하위 그래프를 열거하는 문제를 고려합니다. 입력 그래프의 2-에지 연결 유도 하위 그래프를 열거하는 알고리즘을 제시합니다. Gn 정점과 m 가장자리. 우리의 알고리즘은 2-에지 연결 유도 하위 그래프를 모두 열거합니다. O(n3m|SG|) 시간, 어디서 SG 는 2-에지 연결 유도 하위 그래프의 집합입니다. G. 또한, 알고리즘을 약간 수정하여 다음과 같은 결과를 얻었습니다. O(n3m)-2-에지 연결 유도 하위 그래프에 대한 지연 열거 알고리즘.

발행
IEICE TRANSACTIONS on Information Vol.E105-D No.3 pp.466-473
발행일
2022/03/01
공개일
2021/07/02
온라인 ISSN
1745-1361
DOI
10.1587/transinf.2021FCP0005
원고의 종류
Special Section PAPER (Special Section on Foundations of Computer Science - New Trends of Theory of Computation and Algorithm -)
범주

작성자

Taishu ITO
  Iwate University
Yusuke SANO
  Iwate University
Katsuhisa YAMANAKA
  Iwate University
Takashi HIRAYAMA
  Iwate University

키워드