On some hard and some tractable cases of the maximum acyclic matching problem

DOI10.1007/s10479-019-03311-1zbMath1431.05121arXiv1710.08236OpenAlexW2966046296MaRDI QIDQ2288858

Maximilian Fürst, Dieter Rautenbach

Publication date: 20 January 2020

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1710.08236

zbMATH Keywords

matchinguniquely restricted matchinginduced matchingacyclic matching

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex degrees (05C07)

Related Items (7)

Acyclic Matching in Some Subclasses of Graphs ⋮ Acyclic matchings in graphs of bounded maximum degree ⋮ On the parameterized complexity of the acyclic matching problem ⋮ Acyclic matching in some subclasses of graphs ⋮ Weighted connected matchings ⋮ Matchings under distance constraints. I ⋮ Approximating maximum acyclic matchings by greedy and local search strategies

Cites Work

• Unnamed Item
• On parameterized independent feedback vertex set
• Maximum regular induced subgraphs in \(2P_3\)-free graphs
• On distance-3 matchings and induced matchings
• Matching theory
• NP-completeness of some generalizations of the maximum matching problem
• Induced matchings
• Induced matchings in intersection graphs.
• Degenerate matchings and edge colorings
• Independent feedback vertex set for \(P_5\)-free graphs
• 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
• On the approximability of the maximum induced matching problem
• Generalized subgraph-restricted matchings in graphs
• On maximum induced matchings in bipartite graphs
• New results on maximum induced matchings in bipartite graphs and beyond
• Maximum induced matchings close to maximum matchings
• Equality of distance packing numbers
• The graphs with maximum induced matching and maximum matching the same size
• On the Maximum Uniquely Restricted Matching for Bipartite Graphs
• Uniquely Restricted Matchings in Interval Graphs
• Graphs in which some and every maximum matching is uniquely restricted
• Improved Algorithms and Combinatorial Bounds for Independent Feedback Vertex Set
• ACYCLIC MATCHINGS IN SUBCLASSES OF BIPARTITE GRAPHS
• Independent Set in P₅-Free Graphs in Polynomial Time
• Uniquely restricted matchings

This page was built for publication: On some hard and some tractable cases of the maximum acyclic matching problem