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
본 연구에서는 유도된 일치 열거와 관련된 문제를 해결합니다. 가장자리 세트 M 그래프의 유도된 일치입니다. G=(V,E). 일치 항목의 열거는 문헌에서 널리 연구되었습니다. 그러나 유도된 일치에 대한 연구는 거의 없습니다. 간단한 알고리즘에는 다음이 필요합니다. O(Δ2) 하위 문제를 생성하는 시간에서 나오는 각 솔루션에 대한 시간입니다. 여기서 Δ는 입력 그래프의 최대 차수입니다. 하위 문제를 생성하기 위해 알고리즘은 가장자리를 선택합니다. e 두 개의 그래프를 생성합니다. 하나는 제거하여 얻습니다. e 에 G, 다른 하나는 제거하여 얻습니다. e, 인접한 가장자리 e, 및 인접한 가장자리에 인접한 가장자리 e. 이 작업에는 필요하므로 O(Δ2) 시간, 간단한 알고리즘은 유도된 모든 매칭을 열거합니다. O(Δ2) 솔루션당 시간. 짧은 시간 내에 하위 문제를 생성할 수 있는 로컬 구조를 조사하고 시간 복잡도가 다음과 같다는 것을 증명했습니다. O(1) 입력 그래프가 다음과 같은 경우 C4-무료. 그래프는 C4-해당 하위 그래프 중 길이가 4인 주기가 없는 경우에만 무료입니다.
Kazuhiro KURITA
Hokkaido University
Kunihiro WASA
National Institute of Informatics
Takeaki UNO
National Institute of Informatics
Hiroki ARIMURA
Hokkaido University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
부
Kazuhiro KURITA, Kunihiro WASA, Takeaki UNO, Hiroki ARIMURA, "Efficient Enumeration of Induced Matchings in a Graph without Cycles with Length Four" in IEICE TRANSACTIONS on Fundamentals,
vol. E101-A, no. 9, pp. 1383-1391, September 2018, doi: 10.1587/transfun.E101.A.1383.
Abstract: In this study, we address a problem pertaining to the induced matching enumeration. An edge set M is an induced matching of a graph G=(V,E). The enumeration of matchings has been widely studied in literature; however, there few studies on induced matching. A straightforward algorithm takes O(Δ2) time for each solution that is coming from the time to generate a subproblem, where Δ is the maximum degree in an input graph. To generate a subproblem, an algorithm picks up an edge e and generates two graphs, the one is obtained by removing e from G, the other is obtained by removing e, adjacent edge to e, and edges adjacent to adjacent edge of e. Since this operation needs O(Δ2) time, a straightforward algorithm enumerates all induced matchings in O(Δ2) time per solution. We investigated local structures that enable us to generate subproblems within a short time and proved that the time complexity will be O(1) if the input graph is C4-free. A graph is C4-free if and only if none of its subgraphs have a cycle of length four.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E101.A.1383/_p
부
@ARTICLE{e101-a_9_1383,
author={Kazuhiro KURITA, Kunihiro WASA, Takeaki UNO, Hiroki ARIMURA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Efficient Enumeration of Induced Matchings in a Graph without Cycles with Length Four},
year={2018},
volume={E101-A},
number={9},
pages={1383-1391},
abstract={In this study, we address a problem pertaining to the induced matching enumeration. An edge set M is an induced matching of a graph G=(V,E). The enumeration of matchings has been widely studied in literature; however, there few studies on induced matching. A straightforward algorithm takes O(Δ2) time for each solution that is coming from the time to generate a subproblem, where Δ is the maximum degree in an input graph. To generate a subproblem, an algorithm picks up an edge e and generates two graphs, the one is obtained by removing e from G, the other is obtained by removing e, adjacent edge to e, and edges adjacent to adjacent edge of e. Since this operation needs O(Δ2) time, a straightforward algorithm enumerates all induced matchings in O(Δ2) time per solution. We investigated local structures that enable us to generate subproblems within a short time and proved that the time complexity will be O(1) if the input graph is C4-free. A graph is C4-free if and only if none of its subgraphs have a cycle of length four.},
keywords={},
doi={10.1587/transfun.E101.A.1383},
ISSN={1745-1337},
month={September},}
부
TY - JOUR
TI - Efficient Enumeration of Induced Matchings in a Graph without Cycles with Length Four
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1383
EP - 1391
AU - Kazuhiro KURITA
AU - Kunihiro WASA
AU - Takeaki UNO
AU - Hiroki ARIMURA
PY - 2018
DO - 10.1587/transfun.E101.A.1383
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E101-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2018
AB - In this study, we address a problem pertaining to the induced matching enumeration. An edge set M is an induced matching of a graph G=(V,E). The enumeration of matchings has been widely studied in literature; however, there few studies on induced matching. A straightforward algorithm takes O(Δ2) time for each solution that is coming from the time to generate a subproblem, where Δ is the maximum degree in an input graph. To generate a subproblem, an algorithm picks up an edge e and generates two graphs, the one is obtained by removing e from G, the other is obtained by removing e, adjacent edge to e, and edges adjacent to adjacent edge of e. Since this operation needs O(Δ2) time, a straightforward algorithm enumerates all induced matchings in O(Δ2) time per solution. We investigated local structures that enable us to generate subproblems within a short time and proved that the time complexity will be O(1) if the input graph is C4-free. A graph is C4-free if and only if none of its subgraphs have a cycle of length four.
ER -