On maximum induced matchings in bipartite graphs

DOI10.1016/S0020-0190(01)00185-5zbMath1046.68081OpenAlexW2058511514MaRDI QIDQ1847371

Publication date: 24 June 2003

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(01)00185-5

zbMATH Keywords

bi-complement reducible graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (53)

Disconnected matchings ⋮ Augmenting approach for some maximum set problems ⋮ Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices ⋮ On graphs with induced matching number almost equal to matching number ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Graph matching problems and the NP-hardness of sortedness constraints ⋮ Attribute selection using contranominal scales ⋮ Induced matchings in subcubic graphs without short cycles ⋮ On the parameterized complexity of the acyclic matching problem ⋮ Maximum Induced Matchings in Grids ⋮ Tree-Width and Optimization in Bounded Degree Graphs ⋮ Weighted connected matchings ⋮ Hardness of bounding influence via graph modification ⋮ Boundary Classes of Planar Graphs ⋮ Locally searching for large induced matchings ⋮ Degenerate matchings and edge colorings ⋮ Induced Matching in Some Subclasses of Bipartite Graphs ⋮ Perfectly matched sets in graphs: parameterized and exact computation ⋮ Strong edge-colouring and induced matchings ⋮ Two greedy consequences for maximum induced matchings ⋮ The maximum fuzzy weighted matching models and hybrid genetic algorithm ⋮ NP-hard graph problems and boundary classes of graphs ⋮ Generalizing the induced matching by edge capacity constraints ⋮ Maximum induced matching algorithms via vertex ordering characterizations ⋮ Approximating weighted induced matchings ⋮ Maximum regular induced subgraphs in \(2P_3\)-free graphs ⋮ Induced Matchings in Graphs of Degree at Most 4 ⋮ On the approximability of the maximum induced matching problem ⋮ On distance-3 matchings and induced matchings ⋮ On the complexity of the dominating induced matching problem in hereditary classes of graphs ⋮ Maximum weight induced matching in some subclasses of bipartite graphs ⋮ The complexity of dissociation set problems in graphs ⋮ The induced matching and chain subgraph cover problems for convex bipartite graphs ⋮ New kernels for several problems on planar graphs ⋮ On some hard and some tractable cases of the maximum acyclic matching problem ⋮ Regularity of bicyclic graphs and their powers ⋮ Combinatorics and algorithms for quasi-chain graphs ⋮ Combinatorics and algorithms for quasi-chain graphs ⋮ Induced Matchings in Graphs of Bounded Maximum Degree ⋮ The parameterized complexity of the induced matching problem ⋮ Disconnected matchings ⋮ Dominating Induced Matchings ⋮ On Distance-3 Matchings and Induced Matchings ⋮ Approximating maximum uniquely restricted matchings in bipartite graphs ⋮ Recent progress on strong edge-coloring of graphs ⋮ Brambles and independent packings in chordal graphs ⋮ Independent packings in structured graphs ⋮ Squares of Intersection Graphs and Induced Matchings ⋮ Maximum Induced Matching Algorithms via Vertex Ordering Characterizations ⋮ Moderately exponential time algorithms for the maximum induced matching problem ⋮ Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs

Cites Work

This page was built for publication: On maximum induced matchings in bipartite graphs