Approximating maximum acyclic matchings by greedy and local search strategies
type: Item
instance of: scholarly article
title: Approximating maximum acyclic matchings by greedy and local search strategies
DOI: 10.1007/978-3-030-58150-3_44
author: Julien Baste
author: Maximilian Fürst
author: Dieter Rautenbach
publication date: 2021-04-21T00:00:00Z
Mathematics Subject Classification ID: 68Rxx
zbMATH DE Number: 7336133
zbMATH Keywords: acyclic matching
zbMATH Keywords: induced matching
zbMATH Keywords: greedy algorithm
zbMATH Keywords: local search
MaRDI profile type: Publication
full work available at URL: 978-3-030-58150-3 44
OpenAlex ID: W3082173007
cites work: Linear programming based approximation for unweighted induced matchings -- breaking the \(\varDelta\) barrier
cites work: Degenerate matchings and edge colorings
cites work: The graphs with maximum induced matching and maximum matching the same size
cites work: On the approximability of the maximum induced matching problem
cites work: Uniquely restricted matchings in subcubic graphs
cites work: A lower bound on the acyclic matching number of subcubic graphs
cites work: On some hard and some tractable cases of the maximum acyclic matching problem
cites work: Locally searching for large induced matchings
cites work: Generalized subgraph-restricted matchings in graphs
cites work: Approximation and Online Algorithms
cites work: Induced matchings in subcubic graphs without short cycles
cites work: Induced matchings in graphs of bounded maximum degree
cites work: Induced Matchings in Graphs of Degree at Most 4
cites work: Induced Matchings in Subcubic Graphs
cites work: Finding maximum induced matchings in subclasses of claw-free and \(P_5\)-free graphs, and in graphs with matching and induced matching of equal maximum size
cites work: Approximating weighted induced matchings
cites work: Approximability results for the maximum and minimum maximal induced matching problems
cites work: ACYCLIC MATCHINGS IN SUBCLASSES OF BIPARTITE GRAPHS
cites work: Two greedy consequences for maximum induced matchings
cites work: NP-completeness of some generalizations of the maximum matching problem
cites work: Q4944970
description: scientific article; zbMATH DE number 7336133