Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2016 | 10.1016/j.tcs.2015.11.014 | Theoretical Computer Science |
Keywords | Field | DocType |
Bipartite graph,Convex partition,Graph convexity,Geodesic convexity | Discrete mathematics,Complete bipartite graph,Combinatorics,Graph power,Vertex (graph theory),Bipartite graph,Cycle graph,Neighbourhood (graph theory),Matching (graph theory),Independent set,Mathematics | Journal |
Volume | Issue | ISSN |
609 | P2 | 0304-3975 |
Citations | PageRank | References |
2 | 0.47 | 6 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Luciano N. Grippo | 1 | 28 | 7.79 |
Martín Matamala | 2 | 158 | 21.63 |
Martín Darío Safe | 3 | 23 | 8.99 |
maya stein | 4 | 81 | 15.65 |