# Moderately exponential time algorithms for the maximum induced matching problem

Ontology type: schema:ScholarlyArticle

### Article Info

DATE

2014-10-22

AUTHORS ABSTRACT

An induced matchingM⊆E\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$M\subseteq E$$\end{document} in a graph G=(V,E)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G=(V, E)$$\end{document} is a matching such that no two edges in M\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$M$$\end{document} are joined by any third edge of the graph. The Maximum Induced Matching problem is to find an induced matching of maximum cardinality. It is NP-hard. Branch-and-reduce algorithms proposed in the previous results for the Maximum Induced Matching problem use a standard branching rule: for a vertex v\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$v$$\end{document}, it branches into deg(v)+1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$deg(v)+1$$\end{document} subproblems that either v\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$v$$\end{document} is not an endvertex of any edge in M\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$M$$\end{document} or v\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$v$$\end{document} and one of its neighbor are endvertices of an edge in M\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$M$$\end{document}. In this paper, we give a simple branch-and-reduce algorithm consisting of a boundary condition, a reduction rule, and a branching rule. Especially, the branching rule only branches the original problem into two subproblems. When the algorithm meets the input instance satisfying the boundary condition, we reduce the Maximum Induced Matching problem to the Maximum Independent Set problem. By using the measure-and-conquer approach to analyze the running time of the algorithm, we show that this algorithm runs in time O∗(1.4658n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O^{*}(1.4658^n)$$\end{document} which is faster than previously known algorithms. By adding two branching rules in the simple exact algorithm, we obtain an O∗(1.4321n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O^{*}(1.4321^n)$$\end{document}-time algorithm for the Maximum Induced Matching problem. Moreover, we give a moderately exponential time ρ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\rho$$\end{document}-approximation algorithm, 0<ρ<1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$0 < \rho < 1$$\end{document}, for the Maximum Induced Matching problem. For ρ=0.5\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\rho =0.5$$\end{document}, the algorithm runs in time O∗(1.3348n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O^{*}(1.3348^n)$$\end{document}. More... »

PAGES

981-998

### Journal

TITLE

Optimization Letters

ISSUE

5

VOLUME

9

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s11590-014-0813-z

DOI

http://dx.doi.org/10.1007/s11590-014-0813-z

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1008036174

Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Mathematical Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Applied Mathematics",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0103",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Numerical and Computational Mathematics",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Department of Computer Science and Information Engineering, HungKuang University, 43302, Taichung, Sha Lu, Taiwan",
"id": "http://www.grid.ac/institutes/grid.411432.1",
"name": [
"Department of Computer Science and Information Engineering, HungKuang University, 43302, Taichung, Sha Lu, Taiwan"
],
"type": "Organization"
},
"familyName": "Chang",
"givenName": "Maw-Shang",
"id": "sg:person.013174232477.45",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013174232477.45"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Computer Science and Information Engineering, National Chung Cheng University, 62102, Chiayi, Min-Hsiung, Taiwan",
"id": "http://www.grid.ac/institutes/grid.412047.4",
"name": [
"Department of Computer Science and Information Engineering, National Chung Cheng University, 62102, Chiayi, Min-Hsiung, Taiwan"
],
"type": "Organization"
},
"familyName": "Chen",
"givenName": "Li-Hsuan",
"id": "sg:person.014055212561.22",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014055212561.22"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Computer Science and Information Engineering, HungKuang University, 43302, Taichung, Sha Lu, Taiwan",
"id": "http://www.grid.ac/institutes/grid.411432.1",
"name": [
"Department of Computer Science and Information Engineering, HungKuang University, 43302, Taichung, Sha Lu, Taiwan"
],
"type": "Organization"
},
"familyName": "Hung",
"givenName": "Ling-Ju",
"id": "sg:person.014652573161.60",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014652573161.60"
],
"type": "Person"
}
],
"citation": [
{
"id": "sg:pub.10.1007/s00453-003-1035-4",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1041831380",
"https://doi.org/10.1007/s00453-003-1035-4"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-16533-7",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1012209190",
"https://doi.org/10.1007/978-3-642-16533-7"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-35452-6_7",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1015528043",
"https://doi.org/10.1007/978-3-642-35452-6_7"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-13073-1_26",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1032588828",
"https://doi.org/10.1007/978-3-642-13073-1_26"
],
"type": "CreativeWork"
}
],
"datePublished": "2014-10-22",
"datePublishedReg": "2014-10-22",
"description": "An induced matchingM\u2286E\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$M\\subseteq E$$\\end{document} in a graph G=(V,E)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$G=(V, E)$$\\end{document} is a matching such that no two edges in M\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$M$$\\end{document} are joined by any third edge of the graph. The Maximum Induced Matching problem is to find an induced matching of maximum cardinality. It is NP-hard. Branch-and-reduce algorithms proposed in the previous results for the Maximum Induced Matching problem use a standard branching rule: for a vertex v\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$v$$\\end{document}, it branches into deg(v)+1\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$deg(v)+1$$\\end{document} subproblems that either v\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$v$$\\end{document} is not an endvertex of any edge in M\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$M$$\\end{document} or v\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$v$$\\end{document} and one of its neighbor are endvertices of an edge in M\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$M$$\\end{document}. In this paper, we give a simple branch-and-reduce algorithm consisting of a boundary condition, a reduction rule, and a branching rule. Especially, the branching rule only branches the original problem into two subproblems. When the algorithm meets the input instance satisfying the boundary condition, we reduce the Maximum Induced Matching problem to the Maximum Independent Set problem. By using the measure-and-conquer approach to analyze the running time of the algorithm, we show that this algorithm runs in time O\u2217(1.4658n)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$O^{*}(1.4658^n)$$\\end{document} which is faster than previously known algorithms. By adding two branching rules in the simple exact algorithm, we obtain an O\u2217(1.4321n)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$O^{*}(1.4321^n)$$\\end{document}-time algorithm for the Maximum Induced Matching problem. Moreover, we give a moderately exponential time \u03c1\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\rho$$\\end{document}-approximation algorithm, 0<\u03c1<1\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$0 < \\rho < 1$$\\end{document}, for the Maximum Induced Matching problem. For \u03c1=0.5\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\rho =0.5$$\\end{document}, the algorithm runs in time O\u2217(1.3348n)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$O^{*}(1.3348^n)$$\\end{document}.",
"genre": "article",
"id": "sg:pub.10.1007/s11590-014-0813-z",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": [
{
"id": "sg:journal.1052645",
"issn": [
"1862-4472",
"1862-4480"
],
"name": "Optimization Letters",
"publisher": "Springer Nature",
"type": "Periodical"
},
{
"issueNumber": "5",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
}
],
"keywords": [
"Maximum Induced Matching problem",
"Induced Matching problem",
"matching problem",
"maximum independent set problem",
"exponential time algorithm",
"branching rules",
"independent set problem",
"input instances",
"conquer approach",
"exact algorithm",
"running time",
"simple exact algorithm",
"set problem",
"time algorithm",
"algorithm",
"simple branch",
"reduction rules",
"exponential time",
"maximum cardinality",
"original problem",
"subproblems",
"graph",
"matching",
"rules",
"induced matching",
"neighbors",
"NP",
"edge",
"cardinality",
"third edge",
"instances",
"vertices",
"time",
"endvertices",
"branches",
"endvertex",
"previous results",
"results",
"measures",
"conditions",
"boundary conditions",
"problem",
"paper",
"approach",
"standard branching rule"
],
"name": "Moderately exponential time algorithms for the maximum induced matching problem",
"pagination": "981-998",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1008036174"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s11590-014-0813-z"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s11590-014-0813-z",
"https://app.dimensions.ai/details/publication/pub.1008036174"
],
"sdDataset": "articles",
"sdDatePublished": "2021-11-01T18:22",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/article/article_637.jsonl",
"type": "ScholarlyArticle",
"url": "https://doi.org/10.1007/s11590-014-0813-z"
}
]

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s11590-014-0813-z'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s11590-014-0813-z'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s11590-014-0813-z'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s11590-014-0813-z'

This table displays all metadata directly associated to this object as RDF triples.

140 TRIPLES      22 PREDICATES      75 URIs      62 LITERALS      6 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0102
3 anzsrc-for:0103
4 schema:author N4555321936f245f4a2c61c0c7d1cec06
5 schema:citation sg:pub.10.1007/978-3-642-13073-1_26
6 sg:pub.10.1007/978-3-642-16533-7
7 sg:pub.10.1007/978-3-642-35452-6_7
8 sg:pub.10.1007/s00453-003-1035-4
9 schema:datePublished 2014-10-22
10 schema:datePublishedReg 2014-10-22
11 schema:description An induced matchingM⊆E\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$M\subseteq E$$\end{document} in a graph G=(V,E)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G=(V, E)$$\end{document} is a matching such that no two edges in M\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$M$$\end{document} are joined by any third edge of the graph. The Maximum Induced Matching problem is to find an induced matching of maximum cardinality. It is NP-hard. Branch-and-reduce algorithms proposed in the previous results for the Maximum Induced Matching problem use a standard branching rule: for a vertex v\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$v$$\end{document}, it branches into deg(v)+1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$deg(v)+1$$\end{document} subproblems that either v\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$v$$\end{document} is not an endvertex of any edge in M\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$M$$\end{document} or v\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$v$$\end{document} and one of its neighbor are endvertices of an edge in M\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$M$$\end{document}. In this paper, we give a simple branch-and-reduce algorithm consisting of a boundary condition, a reduction rule, and a branching rule. Especially, the branching rule only branches the original problem into two subproblems. When the algorithm meets the input instance satisfying the boundary condition, we reduce the Maximum Induced Matching problem to the Maximum Independent Set problem. By using the measure-and-conquer approach to analyze the running time of the algorithm, we show that this algorithm runs in time O∗(1.4658n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O^{*}(1.4658^n)$$\end{document} which is faster than previously known algorithms. By adding two branching rules in the simple exact algorithm, we obtain an O∗(1.4321n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O^{*}(1.4321^n)$$\end{document}-time algorithm for the Maximum Induced Matching problem. Moreover, we give a moderately exponential time ρ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\rho$$\end{document}-approximation algorithm, 0<ρ<1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$0 < \rho < 1$$\end{document}, for the Maximum Induced Matching problem. For ρ=0.5\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\rho =0.5$$\end{document}, the algorithm runs in time O∗(1.3348n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O^{*}(1.3348^n)$$\end{document}.
12 schema:genre article
13 schema:inLanguage en
14 schema:isAccessibleForFree false
15 schema:isPartOf N157c275a827149629748f62c603734d8
16 N4533c98129fa417594c0bf69cac2d3fa
17 sg:journal.1052645
18 schema:keywords Induced Matching problem
19 Maximum Induced Matching problem
20 NP
21 algorithm
22 approach
23 boundary conditions
24 branches
25 branching rules
26 cardinality
27 conditions
28 conquer approach
29 edge
30 endvertex
31 endvertices
32 exact algorithm
33 exponential time
34 exponential time algorithm
35 graph
36 independent set problem
37 induced matching
38 input instances
39 instances
40 matching
41 matching problem
42 maximum cardinality
43 maximum independent set problem
44 measures
45 neighbors
46 original problem
47 paper
48 previous results
49 problem
50 reduction rules
51 results
52 rules
53 running time
54 set problem
55 simple branch
56 simple exact algorithm
57 standard branching rule
58 subproblems
59 third edge
60 time
61 time algorithm
62 vertices
63 schema:name Moderately exponential time algorithms for the maximum induced matching problem
64 schema:pagination 981-998
65 schema:productId N5af9f5c55c174ea68451c3673b49dec8
66 Nc35f5d12ae984426b793bcdd6c9bc0d4
67 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008036174
68 https://doi.org/10.1007/s11590-014-0813-z
69 schema:sdDatePublished 2021-11-01T18:22
71 schema:sdPublisher N5dd40bfd3aae435da012ef117e1e75b8
72 schema:url https://doi.org/10.1007/s11590-014-0813-z
74 sgo:sdDataset articles
75 rdf:type schema:ScholarlyArticle
76 N157c275a827149629748f62c603734d8 schema:issueNumber 5
77 rdf:type schema:PublicationIssue
79 rdf:type schema:PublicationVolume
80 N4555321936f245f4a2c61c0c7d1cec06 rdf:first sg:person.013174232477.45
81 rdf:rest N5ed536b4e33b4bd9b56f0008a0e58870
82 N5af9f5c55c174ea68451c3673b49dec8 schema:name dimensions_id
83 schema:value pub.1008036174
84 rdf:type schema:PropertyValue
85 N5dd40bfd3aae435da012ef117e1e75b8 schema:name Springer Nature - SN SciGraph project
86 rdf:type schema:Organization
87 N5ed536b4e33b4bd9b56f0008a0e58870 rdf:first sg:person.014055212561.22
88 rdf:rest Ne66f4501a84649b2857b38512c2cca99
89 Nc35f5d12ae984426b793bcdd6c9bc0d4 schema:name doi
90 schema:value 10.1007/s11590-014-0813-z
91 rdf:type schema:PropertyValue
92 Ne66f4501a84649b2857b38512c2cca99 rdf:first sg:person.014652573161.60
93 rdf:rest rdf:nil
94 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
95 schema:name Mathematical Sciences
96 rdf:type schema:DefinedTerm
97 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
98 schema:name Applied Mathematics
99 rdf:type schema:DefinedTerm
100 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
101 schema:name Numerical and Computational Mathematics
102 rdf:type schema:DefinedTerm
103 sg:journal.1052645 schema:issn 1862-4472
104 1862-4480
105 schema:name Optimization Letters
106 schema:publisher Springer Nature
107 rdf:type schema:Periodical
108 sg:person.013174232477.45 schema:affiliation grid-institutes:grid.411432.1
109 schema:familyName Chang
110 schema:givenName Maw-Shang
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013174232477.45
112 rdf:type schema:Person
113 sg:person.014055212561.22 schema:affiliation grid-institutes:grid.412047.4
114 schema:familyName Chen
115 schema:givenName Li-Hsuan
116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014055212561.22
117 rdf:type schema:Person
118 sg:person.014652573161.60 schema:affiliation grid-institutes:grid.411432.1
119 schema:familyName Hung
120 schema:givenName Ling-Ju
121 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014652573161.60
122 rdf:type schema:Person
123 sg:pub.10.1007/978-3-642-13073-1_26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032588828
124 https://doi.org/10.1007/978-3-642-13073-1_26
125 rdf:type schema:CreativeWork
126 sg:pub.10.1007/978-3-642-16533-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012209190
127 https://doi.org/10.1007/978-3-642-16533-7
128 rdf:type schema:CreativeWork
129 sg:pub.10.1007/978-3-642-35452-6_7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015528043
130 https://doi.org/10.1007/978-3-642-35452-6_7
131 rdf:type schema:CreativeWork
132 sg:pub.10.1007/s00453-003-1035-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041831380
133 https://doi.org/10.1007/s00453-003-1035-4
134 rdf:type schema:CreativeWork
135 grid-institutes:grid.411432.1 schema:alternateName Department of Computer Science and Information Engineering, HungKuang University, 43302, Taichung, Sha Lu, Taiwan
136 schema:name Department of Computer Science and Information Engineering, HungKuang University, 43302, Taichung, Sha Lu, Taiwan
137 rdf:type schema:Organization
138 grid-institutes:grid.412047.4 schema:alternateName Department of Computer Science and Information Engineering, National Chung Cheng University, 62102, Chiayi, Min-Hsiung, Taiwan
139 schema:name Department of Computer Science and Information Engineering, National Chung Cheng University, 62102, Chiayi, Min-Hsiung, Taiwan
140 rdf:type schema:Organization