The parameterized complexity of the induced matching problem
From MaRDI portal
Recommendations
Cites work
- 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?)
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A Parameterized Perspective on Packing Paths of Length Two
- A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
- 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
- Induced matchings
- Induced matchings in intersection graphs.
- Irredundancy in circular arc graphs
- Linear Problem Kernels for NP-Hard Problems on Planar Graphs
- NP-completeness of some generalizations of the maximum matching problem
- New results on induced matchings
- On maximum induced matchings in bipartite graphs
- On the Induced Matching Problem
- On the approximability of the maximum 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
- SOFSEM 2006: Theory and Practice of Computer Science
- Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
- Some results on graphs without long induced paths
- The Lost Continent of Polynomial Time: Preprocessing and Kernelization
- The complexity of irredundant sets parameterized by size
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Treewidth. Computations and approximations
- Treewidth: Characterizations, Applications, and Computations
Cited in
(51)- Parameterized results on acyclic matchings with implications for related problems
- An improved kernel and parameterized algorithm for almost induced matching
- On the Induced Matching Problem
- The complexity of induced minors and related problems
- Maximum regular induced subgraphs in \(2P_3\)-free graphs
- On the induced matching problem
- Planar graph vertex partition for linear problem kernels
- The Parameterized Complexity of the Induced Matching Problem in Planar Graphs
- Exact algorithms for maximum induced matching
- Exploiting c-Closure in Kernelization Algorithms for Graph Problems
- Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack
- On the parameterized complexity of the acyclic matching problem
- Parameterized complexity of perfectly matched sets
- On the approximability of the maximum induced matching problem
- Kernelization: new upper and lower bound techniques
- Parameterized algorithms and kernels for almost induced matching
- From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
- FPT and kernelization algorithms for the induced tree problem
- Exploiting \(c\)-closure in kernelization algorithms for graph problems
- Parameterized complexity of induced \(H\)-matching on claw-free graphs
- On some matching problems under the color-spanning model
- Maximum induced matchings close to maximum matchings
- scientific article; zbMATH DE number 5799830 (Why is no real title available?)
- Improved induced matchings in sparse graphs
- Disconnected matchings
- Disconnected matchings
- Towards optimal kernel for connected vertex cover in planar graphs
- Vertex and edge covers with clustering properties: Complexity and algorithms
- Hardness of computing width parameters based on branch decompositions over the vertex set
- Almost induced matching: linear kernels and parameterized algorithms
- Improved induced matchings in sparse graphs
- Complexity and kernels for bipartition into degree-bounded induced graphs
- 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
- The parameterized complexity of \(k\)-edge induced subgraphs
- Integer Programming Formulations and Benders Decomposition for the Maximum Induced Matching Problem
- Parameterized complexity of finding connected induced subgraphs
- Perfectly matched sets in graphs: parameterized and exact computation
- Kernelization of edge perfect code and its variants
- Hardness of computing width parameters based on branch decompositions over the vertex set
- Approximating weighted induced matchings
- Weighted connected matchings
- On distance-3 matchings and induced matchings
- On graphs with induced matching number almost equal to matching number
- Maximum common induced subgraph parameterized by vertex cover
- Parameterized complexity of induced graph matching on claw-free graphs
- Moderately exponential time algorithms for the maximum induced matching problem
- On the fixed-parameter tractability of some matching problems under the color-spanning model
- \(\mathcal{IV}\)-matching is strongly \textsf{NP}-hard
- On the induced matching problem in Hamiltonian bipartite graphs
- New kernels for several problems on planar graphs
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)
