User: Guest  Login
More Searchfields
Simple search
Title:

Locally searching for large induced matchings

Document type:
Zeitschriftenaufsatz
Author(s):
Fürst, Maximilian; Leichter, Marilena; Rautenbach, Dieter
Non-TUM Co-author(s):
ja
Cooperation:
national
Abstract:
It is an easy observation that a natural greedy approach yields a (d−O(1))-factor approximation algorithm for the maximum induced matching problem in d-regular graphs. The only considerable and non-trivial improvement of this approximation ratio was obtained by Gotthilf and Lewenstein using a combination of the greedy approach and local search, where understanding the performance of the local search was the challenging part of the analysis. We study the performance of their local search when app...     »
Keywords:
adone
Intellectual Contribution:
Discipline-based Research
Journal title:
Theoretical Computer Science
Journal listet in FT50 ranking:
nein
Year:
2018
Fulltext / DOI:
doi:10.1016/j.tcs.2018.02.006
Print-ISSN:
0304-3975
Judgement review:
0
Key publication:
Ja
Peer reviewed:
Ja
International:
Ja
Book review:
Nein
Commissioned:
not commissioned
Professional Journal:
Nein
Technology:
Nein
Interdisciplinarity:
Nein
Mission statement:
;
Ethics and Sustainability:
Nein
 BibTeX
versions