Benutzer: Gast  Login
Mehr Felder
Einfache Suche
Titel:

Locally searching for large induced matchings

Dokumenttyp:
Zeitschriftenaufsatz
Autor(en):
Fürst, Maximilian; Leichter, Marilena; Rautenbach, Dieter
Nicht-TUM Koautoren:
ja
Kooperation:
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...     »
Stichworte:
adone
Intellectual Contribution:
Discipline-based Research
Zeitschriftentitel:
Theoretical Computer Science
Journal gelistet in FT50 Ranking:
nein
Jahr:
2018
Volltext / DOI:
doi:10.1016/j.tcs.2018.02.006
Print-ISSN:
0304-3975
Urteilsbesprechung:
0
Key publication:
Ja
Peer reviewed:
Ja
International:
Ja
Book review:
Nein
commissioned:
not commissioned
Professional Journal:
Nein
Technology:
Nein
Interdisziplinarität:
Nein
Leitbild:
;
Ethics und Sustainability:
Nein
 BibTeX
Versionen