The parameterized complexity of the induced matching problem
From MaRDI portal
Publication:1028465
DOI10.1016/j.dam.2008.07.011zbMath1172.05350OpenAlexW2095912437MaRDI QIDQ1028465
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
Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)
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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Irredundancy in circular arc graphs
- Approximability results for the maximum and minimum maximal induced matching problems
- 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
- NP-completeness of some generalizations of the maximum matching problem
- Induced matchings
- Treewidth. Computations and approximations
- Claw-free graphs---a survey
- Induced matchings in intersection 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
- On the approximability of the maximum induced matching problem
- Finding a maximum induced matching in weakly chordal graphs
- On maximum induced matchings in bipartite graphs
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- The complexity of irredundant sets parameterized by size
- New results on induced matchings
- 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
- Fixed-Parameter Tractability Results for Full-Degree Spanning Tree and Its Dual
- The Lost Continent of Polynomial Time: Preprocessing and Kernelization
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Treewidth: Characterizations, Applications, and Computations
- Divide-and-Color
- Polynomial-time data reduction for dominating set
- Bipartite Domination and Simultaneous Matroid Covers
- On the Induced Matching Problem
- Linear Problem Kernels for NP-Hard Problems on Planar Graphs
- Algorithms – ESA 2004
- Automata, Languages and Programming
- A Parameterized Perspective on Packing Paths of Length Two
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- SOFSEM 2006: Theory and Practice of Computer Science
- Approximation and Online Algorithms
