On the parameterized complexity of the acyclic matching problem
From MaRDI portal
Publication:6038700
DOI10.1016/J.TCS.2023.113862arXiv2109.06004OpenAlexW4362673250MaRDI QIDQ6038700
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
computational complexitytreewidthinduced matchingparameterized complexityacyclic matchingmodular-width
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
Related Items (2)
Minimum maximal acyclic matching in proper interval graphs ⋮ Parameterized results on acyclic matchings with implications for related problems
This page was built for publication: On the parameterized complexity of the acyclic matching problem
