On the parameterized complexity of the acyclic matching problem

DOI10.1016/j.tcs.2023.113862arXiv2109.06004OpenAlexW4362673250MaRDI QIDQ6038700

Sahab Hajebi, Ramin Javadi

Publication date: 2 May 2023

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

computational complexitytreewidthinduced matchingparameterized complexityacyclic matchingmodular-width

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parameterized complexity of induced graph matching on claw-free graphs
• Irredundancy in circular arc graphs
• The parameterized complexity of the induced matching problem
• Some results on graphs without long induced paths
• Simple upper bounds for partition functions
• NP-completeness of some generalizations of the maximum matching problem
• Induced matchings
• Treewidth. Computations and approximations
• Induced matchings in intersection graphs.
• Asymptotic bounds for some bipartite graph: Complete graph Ramsey numbers
• Degenerate matchings and edge colorings
• 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
• Generalized subgraph-restricted matchings in graphs
• Finding a maximum induced matching in weakly chordal graphs
• On maximum induced matchings in bipartite graphs
• Parameterized complexity of finding subgraphs with hereditary properties.
• The complexity of irredundant sets parameterized by size
• New results on induced matchings
• On the tree-width of even-hole-free graphs
• Approximating maximum acyclic matchings by greedy and local search strategies
• On the induced matching problem in Hamiltonian bipartite graphs
• Ramsey numbers and bipartite Ramsey numbers via quasi-random graphs
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• On some hard and some tractable cases of the maximum acyclic matching problem
• Planarity of iterated line graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Acyclic matching in some subclasses of graphs
• Parameterized Algorithms for Modular-Width
• On two geometric problems related to the travelling salesman problem
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• On feedback vertex sets and nonseparating independent sets in cubic graphs
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• Color-coding
• Bipartite Domination and Simultaneous Matroid Covers
• ACYCLIC MATCHINGS IN SUBCLASSES OF BIPARTITE GRAPHS
• Branching and Treewidth Based Exact Algorithms
• Parameterized Algorithms
• Characterizations of derived graphs

This page was built for publication: On the parameterized complexity of the acyclic matching problem