The parameterized complexity of the induced matching problem

From MaRDI portal
Publication:1028465

DOI10.1016/j.dam.2008.07.011zbMath1172.05350OpenAlexW2095912437MaRDI QIDQ1028465

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



Related Items

Disconnected matchings, Exploiting $c$-Closure in Kernelization Algorithms for Graph Problems, 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, Unnamed Item, Unnamed Item, Planar graph vertex partition for linear problem kernels, On the complexity of various parameterizations of common induced subgraph isomorphism, Exact algorithms for maximum induced matching, Improved induced matchings in sparse graphs, Parameterized complexity of perfectly matched sets, On the parameterized complexity of the acyclic matching problem, Parameterized complexity of finding connected induced subgraphs, Weighted connected matchings, From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More, FPT and kernelization algorithms for the induced tree problem, Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack, Towards optimal kernel for connected vertex cover in planar graphs, Perfectly matched sets in graphs: parameterized and exact computation, Parameterized algorithms and kernels for almost induced matching, Hardness of computing width parameters based on branch decompositions over the vertex set, Maximum common induced subgraph parameterized by vertex cover, Integer Programming Formulations and Benders Decomposition for the Maximum Induced Matching Problem, Hardness of computing width parameters based on branch decompositions over the vertex set, On the Fixed-Parameter Tractability of Some Matching Problems Under the Color-Spanning Model, Exploiting c-Closure in Kernelization Algorithms for Graph Problems, Approximating weighted induced matchings, Maximum regular induced subgraphs in \(2P_3\)-free graphs, On distance-3 matchings and induced matchings, New kernels for several problems on planar graphs, The parameterized complexity of \(k\)-edge induced subgraphs, On the induced matching problem in Hamiltonian bipartite graphs, Vertex and edge covers with clustering properties: Complexity and algorithms, Disconnected matchings, On some matching problems under the color-spanning model, Kernelization: New Upper and Lower Bound Techniques, Improved Induced Matchings in Sparse Graphs, Maximum induced matchings close to maximum matchings, Moderately exponential time algorithms for the maximum induced matching problem



Cites Work