Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs

DOI10.1007/s00453-021-00904-wOpenAlexW2769128044MaRDI QIDQ2118390

Boris Klemz, Günter Rote

Publication date: 22 March 2022

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-021-00904-w

zbMATH Keywords

dynamic programminggraph algorithminduced matchingconvex bipartite graphcertifying algorithmchain cover

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items (2)

Computational complexity aspects of super domination ⋮ Weighted connected matchings

Cites Work

• Certifying algorithms
• Linear-time algorithm for the paired-domination problem in convex bipartite graphs
• An 0(n log n) algorithm for the convex bipartite matching problem
• NP-completeness results for some problems on subclasses of bipartite and chordal graphs
• The induced matching and chain subgraph cover problems for convex bipartite graphs
• Algorithms for maximum independent set in convex bipartite graphs
• Maximum induced matchings for chordal graphs in linear time
• NP-completeness of some generalizations of the maximum matching problem
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Induced matchings
• On the complexity of the k-chain subgraph cover problem
• Efficient graph representations
• Induced matchings in asteroidal triple-free 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
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A linear time algorithm for maximum matchings in convex, bipartite graphs
• HAMILTONian circuits in chordal bipartite graphs
• New results on induced matchings
• Maximum weight induced matching in some subclasses of bipartite graphs
• Matchings in Node-Weighted Convex Bipartite Graphs
• Induced Matching in Some Subclasses of Bipartite Graphs
• Covering the edges with consecutive sets
• Maximum matching in a convex bipartite graph
• Difference graphs

This page was built for publication: Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs