Parameterized results on acyclic matchings with implications for related problems
DOI10.1016/J.JCSS.2024.103599MaRDI QIDQ6655671
Publication date: 27 December 2024
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
uniquely restricted matchinginduced matchingparameterized algorithmsacyclic matchingkernelization lower boundsbelow-guarantee parameterization
Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Fundamentals of parameterized complexity
- Improved induced matchings in sparse graphs
- On the induced matching problem
- The generalized matcher game
- Parameterized complexity of finding regular induced subgraphs
- The parameterized complexity of the induced matching problem
- Matching theory
- Algorithmic proofs of two relations between connectivity and the 1- factors of a graph
- NP-completeness of some generalizations of the maximum matching problem
- Induced matchings
- Uniquely restricted matchings and edge colorings
- The matcher game played in graphs
- Degenerate matchings and edge colorings
- Generalized subgraph-restricted matchings in graphs
- Approximating maximum acyclic matchings by greedy and local search strategies
- Maximum weight induced matching in some subclasses of bipartite graphs
- Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs
- Parameterized algorithms and kernels for almost induced matching
- On some hard and some tractable cases of the maximum acyclic matching problem
- Acyclic matching in some subclasses of graphs
- Uniquely Restricted Matchings in Interval Graphs
- Bipartite Domination and Simultaneous Matroid Covers
- ACYCLIC MATCHINGS IN SUBCLASSES OF BIPARTITE GRAPHS
- Kernelization Lower Bounds by Cross-Composition
- Upper bounds on the uniquely restricted chromatic index
- Algorithmics of Matching Under Preferences
- Parameterized Algorithms
- Large Induced Matchings in Random Graphs
- On the complexity of minimum maximal uniquely restricted matching
- Uniquely restricted matchings
- Disconnected matchings
- On the parameterized complexity of the acyclic matching problem
- Constant approximating k-clique is w[1]-hard
- Parameterized Results on Acyclic Matchings with Implications for Related Problems
- $\mathcal{P}$-matchings Parameterized by Treewidth
- On an estimate of the chromatic class of a \(p\)-graph
- Induced matching below guarantees: average paves the way for fixed-parameter tractability
- On the complexity of minimum maximal acyclic matchings
This page was built for publication: Parameterized results on acyclic matchings with implications for related problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6655671)