IEICE TRANSACTIONS on Fundamentals
Efficient Enumeration of Induced Matchings in a Graph without Cycles with Length Four
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E101-A No.9 pp.1383-1391
- Publication Date
- 2018/09/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E101.A.1383
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Kazuhiro KURITA
Hokkaido University
Kunihiro WASA
National Institute of Informatics
Takeaki UNO
National Institute of Informatics
Hiroki ARIMURA
Hokkaido University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
Copy
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
Copy
@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},}
Copy
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 -
English
