Induced Matching in Some Subclasses of Bipartite Graphs

DOI10.1007/978-3-319-53007-9_27zbMath1485.68196OpenAlexW2583364872MaRDI QIDQ2971661

Manav Kashyap, B. S. Panda, Piyush Dane, Arti Pandey

Publication date: 7 April 2017

Published in: Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-53007-9_27

zbMATH Keywords

matchinggraph algorithmNP-completenessbipartite graphsinduced matching

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

Maximum weight induced matching in some subclasses of bipartite graphs ⋮ Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs

Cites Work

• Unnamed Item
• Circular convex bipartite graphs: feedback vertex sets
• Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs
• Feedback vertex sets on restricted bipartite graphs
• The induced matching and chain subgraph cover problems for convex bipartite graphs
• NP-completeness of some generalizations of the maximum matching problem
• Induced matchings
• Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits
• 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
• New results on induced matchings
• Independent Domination on Tree Convex Bipartite Graphs
• Perfect Elimination and Chordal Bipartite Graphs
• Tractable Connected Domination for Restricted Bipartite Graphs (Extended Abstract)
• Domination in Some Subclasses of Bipartite Graphs
• Restricted Bipartite Graphs: Comparison and Hardness Results

This page was built for publication: Induced Matching in Some Subclasses of Bipartite Graphs