Linear-Time Algorithms for Maximum-Weight Induced Matchings and Minimum Chain Covers in Convex Bipartite Graphs

Boris Klemz, Günter Rote

A bipartite graph $G=(U,V,E)$ is convex if the vertices in $V$ can be linearly ordered such that for each vertex $u\in U$, the neighbors of $u$ are consecutive in the ordering of $…