Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs
type: Item
instance of: scholarly article
title: Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs
author: Boris Klemz
author: Günter Rote
published in: Algorithmica
publication date: 2022-03-22T00:00:00Z
Mathematics Subject Classification ID: 68Wxx
Mathematics Subject Classification ID: 05Cxx
zbMATH DE Number: 7495634
zbMATH Keywords: graph algorithm
zbMATH Keywords: induced matching
zbMATH Keywords: chain cover
zbMATH Keywords: convex bipartite graph
zbMATH Keywords: certifying algorithm
zbMATH Keywords: dynamic programming
MaRDI profile type: Publication
full work available at URL: s00453-021-00904-w
OpenAlex ID: W2769128044
cites work: NP-completeness results for some problems on subclasses of bipartite and chordal graphs
cites work: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
cites work: The induced matching and chain subgraph cover problems for convex bipartite graphs
cites work: Maximum induced matchings for chordal graphs in linear time
cites work: Induced matchings
cites work: Finding a maximum induced matching in weakly chordal graphs
cites work: Induced matchings in asteroidal triple-free graphs
cites work: Covering the edges with consecutive sets
cites work: On the approximability of the maximum induced matching problem
cites work: An 0(n log n) algorithm for the convex bipartite matching problem
cites work: Maximum matching in a convex bipartite graph
cites work: New results on induced matchings
cites work: Difference graphs
cites work: Linear-time algorithm for the paired-domination problem in convex bipartite graphs
cites work: Matchings in node-weighted convex bipartite graphs
cites work: 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
cites work: On maximum induced matchings in bipartite graphs
cites work: Certifying algorithms
cites work: HAMILTONian circuits in chordal bipartite graphs
cites work: Maximum weight induced matching in some subclasses of bipartite graphs
cites work: Induced Matching in Some Subclasses of Bipartite Graphs
cites work: Combinatorial optimization. Polyhedra and efficiency (3 volumes)
cites work: Algorithms for maximum independent set in convex bipartite graphs
cites work: Efficient graph representations
cites work: A linear time algorithm for maximum matchings in convex, bipartite graphs
cites work: NP-completeness of some generalizations of the maximum matching problem
cites work: On the complexity of the k-chain subgraph cover problem
DOI: 10.1007/S00453-021-00904-W
description: scientific article; zbMATH DE number 7495634