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

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

Efficient Enumeration of Induced Matchings in a Graph without Cycles with Length Four 길이가 XNUMX인 순환이 없는 그래프에서 유도된 일치의 효율적인 열거

Kazuhiro KURITA, Kunihiro WASA, Takeaki UNO, Hiroki ARIMURA

  • 조회수

    0

  • 이것을 인용

요약 :

본 연구에서는 유도된 일치 열거와 관련된 문제를 해결합니다. 가장자리 세트 M 그래프의 유도된 일치입니다. G=(V,E). 일치 항목의 열거는 문헌에서 널리 연구되었습니다. 그러나 유도된 일치에 대한 연구는 거의 없습니다. 간단한 알고리즘에는 다음이 필요합니다. O2) 하위 문제를 생성하는 시간에서 나오는 각 솔루션에 대한 시간입니다. 여기서 Δ는 입력 그래프의 최대 차수입니다. 하위 문제를 생성하기 위해 알고리즘은 가장자리를 선택합니다. e 두 개의 그래프를 생성합니다. 하나는 제거하여 얻습니다. eG, 다른 하나는 제거하여 얻습니다. e, 인접한 가장자리 e, 및 인접한 가장자리에 인접한 가장자리 e. 이 작업에는 필요하므로 O2) 시간, 간단한 알고리즘은 유도된 모든 매칭을 열거합니다. O2) 솔루션당 시간. 짧은 시간 내에 하위 문제를 생성할 수 있는 로컬 구조를 조사하고 시간 복잡도가 다음과 같다는 것을 증명했습니다. O(1) 입력 그래프가 다음과 같은 경우 C4-무료. 그래프는 C4-해당 하위 그래프 중 길이가 4인 주기가 없는 경우에만 무료입니다.

발행
IEICE TRANSACTIONS on Fundamentals Vol.E101-A No.9 pp.1383-1391
발행일
2018/09/01
공개일
온라인 ISSN
1745-1337
DOI
10.1587/transfun.E101.A.1383
원고의 종류
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
범주

작성자

Kazuhiro KURITA
  Hokkaido University
Kunihiro WASA
  National Institute of Informatics
Takeaki UNO
  National Institute of Informatics
Hiroki ARIMURA
  Hokkaido University

키워드