On the induced matching problem in Hamiltonian bipartite graphs

DOI10.1515/GMJ-2021-2090MaRDI QIDQ2059914zbMATH OpenOpenAlexFDO

Authors Yinglei Song

Publication date 13 December 2021

Published in Georgian Mathematical Journal (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.0864

zbMATH Keywords

inapproximabilityinduced matchingparameterized complexityHamiltonian bipartite graphs

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• New results on maximum induced matchings in bipartite graphs and beyond
• On maximum induced matchings in bipartite graphs
• Induced matchings
• scientific article; zbMATH DE number 5799830
• Approximability results for the maximum and minimum maximal induced matching problems

Cites work

• scientific article; zbMATH DE number 3523580 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• scientific article; zbMATH DE number 1420901 (Why is no real title available?)
• Approximating maximum independent sets by excluding subgraphs
• Approximation algorithms for NP-complete problems on planar graphs
• Approximation algorithms for combinatorial problems
• Efficient algorithms for finding maximum matching in graphs
• Finding a maximum induced matching in weakly chordal graphs
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Improved Parameterized Upper Bounds for Vertex Cover
• Induced matchings in intersection graphs.
• Linear FPT reductions and computational lower bounds
• Maximum matching in multi-interface networks
• On the Induced Matching Problem
• On the approximability of the maximum induced matching problem
• Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs
• Parameterized dominating set problem in chordal graphs: Complexity and lower bound
• Spider web networks: a family of optimal, fault tolerant, Hamiltonian bipartite graphs
• The Parameterized Complexity of the Induced Matching Problem in Planar Graphs
• The complexity of irredundant sets parameterized by size
• The importance of being biased
• The parameterized complexity of the induced matching problem

Cited in

(6)

• Induced Matching in Some Subclasses of Bipartite Graphs
• Induced matchings in bipartite graphs
• Maximum induced matching problem on hhd-free graphs
• On the parameterized complexity of the acyclic matching problem
• On maximum induced matchings in bipartite graphs
• New results on maximum induced matchings in bipartite graphs and beyond

This page was built for publication: On the induced matching problem in Hamiltonian bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2059914)