User: Guest  Login
Document type:
Zeitschriftenaufsatz 
Author(s):
Fürst, Maximilian; Leichter, Marilena; Rautenbach, Dieter 
Non-TUM Co-author(s):
ja 
Cooperation:
national 
Title:
Locally searching for large induced matchings 
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...    »
 
Journal title:
Theoretical Computer Science 
Journal listet in FT50 ranking:
nein 
Year:
2018 
Print-ISSN:
0304-3975 
Key publication:
Ja 
Peer reviewed:
Ja 
International:
Ja 
Book review:
Nein 
Commissioned:
not commissioned 
Professional Journal:
Nein 
Interdisciplinarity:
Nein 
Mission statement:
Ethics and Sustainability:
Nein