On Resource Bipartitioning Problem
Zalia Shams, Shahina Ferdous, Kazi Zakia Sultana, Md. Saidur Rahman · 2006
Given a connected graph G = (V, E), two distinct base vertices u1, u2 ∈ V, a set Vr⊆ V of r special vertices and two natural numbersr1,r2such thatr1+r2= r, we wish to find a partition V1, V2of the vertex set V such thatu1∈ V1,u2∈ V2, Viinduces a connected subgraph Giof G for each i, 1 ≤ i ≤ 2,V2containsr2, vertices from Vrand V2containsr2vertices from V2. We call a vertex in Vra resource vertex and call the above problem of finding a partition as the resource bipartitioning problem. In this paper, we give a simple linear-time algorithm to find such a bipartition of "path-reducible graphs". We also give an algorithm for finding a resource bipartition of a connected graph G where all resource vertices are contained in the same biconnected component of G. We also show that a well-known class of graphs namely "series-parallel graphs" admits a resource bipartitioning. Our algorithm is based on st-numbering of G.