Computing and Combinatorics, 2020, Vol.12273, p.542-553
2020
Details
- Autor(en) / Beteiligte
- Titel
- Approximating Maximum Acyclic Matchings by Greedy and Local Search Strategies
- Ist Teil von
- Computing and Combinatorics, 2020, Vol.12273, p.542-553
- Ort / Verlag
- Switzerland: Springer International Publishing AG
- Erscheinungsjahr
- 2020
- Link zum Volltext
- Quelle
- Alma/SFX Local Collection
- Beschreibungen/Notizen
- A matching M in a graph G is acyclic if the subgraph of G induced by the vertices that are incident to an edge in M is a forest. Even restricted to graphs of bounded maximum degree, the maximum acyclic matching problem is hard. We contribute efficient approximation algorithms for this problem, based on greedy and local search strategies, that have performance guarantees involving the maximum degree of the input graphs.
- Sprache
- Englisch
- Identifikatoren
- ISBN: 9783030581497, 3030581497ISSN: 0302-9743eISSN: 1611-3349DOI: 10.1007/978-3-030-58150-3_44Titel-ID: cdi_springer_books_10_1007_978_3_030_58150_3_44
- Format
- –
- Schlagworte
- Acyclic matching, Greedy algorithm, Induced matching, Local search