On the induced matching problem
DOI10.1016/J.JCSS.2010.09.001zbMATH Open1235.05114OpenAlexW2059738021MaRDI QIDQ657915FDOQ657915
Authors: Iyad Kanj, Michael J. Pelsmajer, Marcus Schaefer, Ge Xia 
Publication date: 11 January 2012
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2008/1361/
Recommendations
Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Applications of a Planar Separator Theorem
- Parameterized complexity of finding regular induced subgraphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Problems and results in extremal combinatorics. I.
- Title not available (Why is that?)
- Title not available (Why is that?)
- Large induced forests in triangle-free planar graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the approximability of the maximum induced matching problem
- Tight bounds on maximal and maximum matchings
- Maximum induced linear forests in outerplanar graphs
- The Parameterized Complexity of the Induced Matching Problem in Planar Graphs
Cited In (28)
- Maximum matching in multi-interface networks
- A faster algorithm for maximum independent set on interval filament graphs
- Integer Programming Formulations and Benders Decomposition for the Maximum Induced Matching Problem
- Bounding the Mim-Width of Hereditary Graph Classes.
- Almost induced matching: linear kernels and parameterized algorithms
- On the Induced Matching Problem
- Exploiting c-Closure in Kernelization Algorithms for Graph Problems
- Parameterized algorithms and kernels for almost induced matching
- Maximum induced matching of hexagonal graphs
- Exact algorithms for maximum induced matching
- Essentially tight kernels for (weakly) closed graphs
- Improved induced matchings in sparse graphs
- Induced packing of odd cycles in planar graphs
- Exploiting \(c\)-closure in kernelization algorithms for graph problems
- The parameterized complexity of the induced matching problem
- On the Problem of Multiple Matching
- Moderately exponential time algorithms for the maximum induced matching problem
- An improved kernel and parameterized algorithm for almost induced matching
- Parameterized complexity of perfectly matched sets
- New kernels for several problems on planar graphs
- On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability
- A simple matching domain with indifferences and a master list
- The Parameterized Complexity of the Induced Matching Problem in Planar Graphs
- Parameterized results on acyclic matchings with implications for related problems
- Bounding the mim‐width of hereditary graph classes
- The minimum number of maximal independent sets in twin-free graphs
- On the approximability of the maximum induced matching problem
- Perfectly matched sets in graphs: parameterized and exact computation
This page was built for publication: On the induced matching problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q657915)
