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
Dans cette étude, nous abordons un problème relatif au dénombrement par correspondance induite. Un ensemble de bords M est une correspondance induite d'un graphe G=(V,E). L'énumération des appariements a été largement étudiée dans la littérature ; cependant, il existe peu d'études sur l'appariement induit. Un algorithme simple prend O(Δ2) temps pour chaque solution issue du temps nécessaire pour générer un sous-problème, où Δ est le degré maximum dans un graphe d'entrée. Pour générer un sous-problème, un algorithme capte une arête e et génère deux graphiques, celui-ci est obtenu en supprimant e du G, l'autre est obtenu en supprimant e, bord adjacent à e, et les bords adjacents au bord adjacent de e. Puisque cette opération nécessite O(Δ2) temps, un algorithme simple énumère toutes les correspondances induites dans O(Δ2) temps par solution. Nous avons étudié les structures locales qui nous permettent de générer des sous-problèmes en peu de temps et avons prouvé que la complexité temporelle sera O(1) si le graphique d'entrée est C4-gratuit. Un graphique est C4-free si et seulement si aucun de ses sous-graphes n'a de cycle de longueur quatre.
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.
Copier
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
Copier
@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},}
Copier
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 -