The search functionality is under construction.

The search functionality is under construction.

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 *C*_{4}-free. A graph is *C*_{4}-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

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.

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 *C*_{4}-free. A graph is *C*_{4}-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 *C*_{4}-free. A graph is *C*_{4}-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 *C*_{4}-free. A graph is *C*_{4}-free if and only if none of its subgraphs have a cycle of length four.

ER -