Convex p-partitions of bipartite graphs
Convex p-partitions of bipartite graphs
复制标题
二分图的凸 p 划分
DOI：
10.1016/j.tcs.2015.11.014
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
M. Stein
中科院分区：
文献类型：
--
作者：
L. N. Grippo;M. Matamala;M. Safe;M. Stein
一个图G的顶点集X是凸的，如果X中两个顶点之间的最短路不包含X外的顶点。证明了当p≥ 1时，二部图的顶点集到p个凸集的所有划分都可以在多项式时间内求出.
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≥ 1, all partitions of the vertex set of a bipartite graph into p convex sets can be found in polynomial time.