The parameterized complexity of the induced matching problem
From MaRDI portal
Recommendations
Cites work
- A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A Parameterized Perspective on Packing Paths of Length Two
- Algorithms – ESA 2004
- Approximability results for the maximum and minimum maximal induced matching problems
- Approximation and Online Algorithms
- Automata, Languages and Programming
- Bipartite Domination and Simultaneous Matroid Covers
- Claw-free graphs---a survey
- Divide-and-Color
- Finding a maximum induced matching in weakly chordal 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
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- Fixed-Parameter Tractability Results for Full-Degree Spanning Tree and Its Dual
- scientific article; zbMATH DE number 2086260 (Why is no real title available?)
- scientific article; zbMATH DE number 434499 (Why is no real title available?)
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- scientific article; zbMATH DE number 1361465 (Why is no real title available?)
- scientific article; zbMATH DE number 1420901 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- Induced matchings
- Induced matchings in intersection graphs.
- Irredundancy in circular arc graphs
- Linear Problem Kernels for NP-Hard Problems on Planar Graphs
- New results on induced matchings
- NP-completeness of some generalizations of the maximum matching problem
- On maximum induced matchings in bipartite graphs
- On the approximability of the maximum induced matching problem
- On the Induced Matching Problem
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Parametrized complexity theory.
- Polynomial-time data reduction for dominating set
- Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
- SOFSEM 2006: Theory and Practice of Computer Science
- Some results on graphs without long induced paths
- The complexity of irredundant sets parameterized by size
- The Lost Continent of Polynomial Time: Preprocessing and Kernelization
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Treewidth. Computations and approximations
- Treewidth: Characterizations, Applications, and Computations
Cited in
(61)- Vertex and edge covers with clustering properties: Complexity and algorithms
- The complexity of induced minors and related problems
- Approximating weighted induced matchings
- On the approximability of the maximum induced matching problem
- Towards optimal kernel for connected vertex cover in planar graphs
- On the induced matching problem in Hamiltonian bipartite graphs
- Parameterized algorithms and kernels for almost induced matching
- New kernels for several problems on planar graphs
- On some matching problems under the color-spanning model
- Maximum induced matchings close to maximum matchings
- Moderately exponential time algorithms for the maximum induced matching problem
- Exact algorithms for maximum induced matching
- Maximum common induced subgraph parameterized by vertex cover
- \(\mathcal{IV}\)-matching is strongly \textsf{NP}-hard
- FPT and kernelization algorithms for the induced tree problem
- Perfectly matched sets in graphs: parameterized and exact computation
- Parameterized complexity of induced H-matching on claw-free graphs
- scientific article; zbMATH DE number 5799830 (Why is no real title available?)
- Kernelization of edge perfect code and its variants
- Almost induced matching: linear kernels and parameterized algorithms
- On graphs with induced matching number almost equal to matching number
- Planar graph vertex partition for linear problem kernels
- The Parameterized Complexity of the Induced Matching Problem in Planar Graphs
- Kernelization: new upper and lower bound techniques
- Improved induced matchings in sparse graphs
- On the fixed-parameter tractability of some matching problems under the color-spanning model
- Solving the problem of finding an independent \(\{K_1,K_2\}\)-packing of maximum weight on graphs of bounded treewidth
- Solving the problem of finding an independent \(\{K_1,K_2\}\)-packing of maximum weight on graphs with special blocks
- Parameterized complexity of induced graph matching on claw-free graphs
- On the Induced Matching Problem
- Exploiting c-closure in kernelization algorithms for graph problems
- From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
- Integer Programming Formulations and Benders Decomposition for the Maximum Induced Matching Problem
- Exploiting c-Closure in Kernelization Algorithms for Graph Problems
- Hardness of computing width parameters based on branch decompositions over the vertex set
- Hardness of computing width parameters based on branch decompositions over the vertex set
- Disconnected matchings
- Disconnected matchings
- Parameterized complexity of perfectly matched sets
- On the parameterized complexity of the acyclic matching problem
- Improved induced matchings in sparse graphs
- Weighted connected matchings
- Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack
- On the induced matching problem
- An improved kernel and parameterized algorithm for almost induced matching
- Parameterized results on acyclic matchings with implications for related problems
- Complexity of deciding the equality of matching numbers
- Parameterized complexity of disconnected matchings
- Maximum regular induced subgraphs in 2P₃-free graphs
- Contractions in perfect graphs
- Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
- \(\mathcal{P}\)-matchings parameterized by treewidth
- Parameterized complexity of perfectly matched sets
- An improved kernel and parameterized algorithm for deletion to induced matching
- Weighted connected matchings
- On distance-3 matchings and induced matchings
- Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
- Structural parameterizations for induced and acyclic matching
- The parameterized complexity of k-edge induced subgraphs
- Complexity and kernels for bipartition into degree-bounded induced graphs
- Parameterized complexity of finding connected induced subgraphs
This page was built for publication: The parameterized complexity of the induced matching problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1028465)
