The parameterized complexity of the induced matching problem
From MaRDI portal
Publication:1028465
DOI10.1016/J.DAM.2008.07.011zbMATH Open1172.05350OpenAlexW2095912437MaRDI QIDQ1028465FDOQ1028465
Authors: Hannes Moser, Somnath Sikdar 
Publication date: 30 June 2009
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2008.07.011
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Claw-free graphs---a survey
- A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
- Parametrized complexity theory.
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Some results on graphs without long induced paths
- Induced matchings
- Treewidth. Computations and approximations
- On maximum induced matchings in bipartite graphs
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Polynomial-time data reduction for dominating set
- Linear Problem Kernels for NP-Hard Problems on Planar Graphs
- Treewidth: Characterizations, Applications, and Computations
- NP-completeness of some generalizations of the maximum matching problem
- 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
- Title not available (Why is that?)
- On the approximability of the maximum induced matching problem
- New results on induced matchings
- A Parameterized Perspective on Packing Paths of Length Two
- Induced matchings in intersection graphs.
- Finding a maximum induced matching in weakly chordal graphs
- Bipartite Domination and Simultaneous Matroid Covers
- Approximability results for the maximum and minimum maximal induced matching problems
- Divide-and-Color
- Title not available (Why is that?)
- Algorithms – ESA 2004
- SOFSEM 2006: Theory and Practice of Computer Science
- The Lost Continent of Polynomial Time: Preprocessing and Kernelization
- Fixed-Parameter Tractability Results for Full-Degree Spanning Tree and Its Dual
- Automata, Languages and Programming
- Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
- Approximation and Online Algorithms
- Irredundancy in circular arc graphs
- On the Induced Matching Problem
- The complexity of irredundant sets parameterized by size
- Title not available (Why is that?)
Cited In (51)
- An improved kernel and parameterized algorithm for almost induced matching
- Parameterized results on acyclic matchings with implications for related problems
- Integer Programming Formulations and Benders Decomposition for the Maximum Induced Matching Problem
- Kernelization: new upper and lower bound techniques
- Hardness of computing width parameters based on branch decompositions over the vertex set
- 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
- Improved induced matchings in sparse graphs
- On the induced matching problem
- Title not available (Why is that?)
- Parameterized complexity of finding connected induced subgraphs
- From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
- Maximum regular induced subgraphs in \(2P_3\)-free graphs
- Approximating weighted induced matchings
- Almost induced matching: linear kernels and parameterized algorithms
- FPT and kernelization algorithms for the induced tree problem
- \(\mathcal{IV}\)-matching is strongly \textsf{NP}-hard
- On the Induced Matching Problem
- Exploiting c-Closure in Kernelization Algorithms for Graph Problems
- Parameterized algorithms and kernels for almost induced matching
- Exact algorithms for maximum induced matching
- On some matching problems under the color-spanning model
- Complexity and kernels for bipartition into degree-bounded induced graphs
- The parameterized complexity of \(k\)-edge induced subgraphs
- Planar graph vertex partition for linear problem kernels
- Hardness of computing width parameters based on branch decompositions over the vertex set
- On the parameterized complexity of the acyclic matching problem
- Improved induced matchings in sparse graphs
- Weighted connected matchings
- Kernelization of edge perfect code and its variants
- Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack
- Maximum common induced subgraph parameterized by vertex cover
- On graphs with induced matching number almost equal to matching number
- Exploiting \(c\)-closure in kernelization algorithms for graph problems
- Disconnected matchings
- Disconnected matchings
- Moderately exponential time algorithms for the maximum induced matching problem
- Parameterized complexity of perfectly matched sets
- Vertex and edge covers with clustering properties: Complexity and algorithms
- Parameterized complexity of induced graph matching on claw-free graphs
- New kernels for several problems on planar graphs
- The Parameterized Complexity of the Induced Matching Problem in Planar Graphs
- Towards optimal kernel for connected vertex cover in planar graphs
- On distance-3 matchings and induced matchings
- On the Fixed-Parameter Tractability of Some Matching Problems Under the Color-Spanning Model
- The complexity of induced minors and related problems
- On the approximability of the maximum induced matching problem
- Perfectly matched sets in graphs: parameterized and exact computation
- On the induced matching problem in Hamiltonian bipartite graphs
- Parameterized complexity of induced \(H\)-matching on claw-free graphs
- Maximum induced matchings close to maximum matchings
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)
