Convex $p$-partitions of bipartite graphs

Resumen

A set of vertices $X$ of a graph $G$ is convex if no shortest path between two vertices in $X$ contains a vertex outside $X$. We prove that for fixed $p\geq 1$, all partitions of the vertex set of a bipartite graph into $p$ convex sets can be found in polynomial time.

Publicación
Theoretical Computer Science 609(2) (2016), 511–514