TY - GEN

T1 - On resource bipartitioning problem

AU - Shams, Zalia

AU - Ferdous, Shahina

AU - Sultana, Kazi Zakia

AU - Rahman, Md Saidur

PY - 2006/1/1

Y1 - 2006/1/1

N2 - Given a connected graph G = (V, E), two distinct base vertices u 1 ,u2 ∈ Vr, a set Vr ⊆ V of r special vertices and two natural numbers r1,r2 such that r1 + r2 = r, we wish to find a partition V 1, V2 of the vertex set V such that u1 ∈, V1, u2 ∈ V2, Vi induces a connected subgraph Gi of G for each i, 1 ≤ i ≤ 2, V1 contains r1 vertices from Vr and V2 contains r2 vertices from Vr. We call a vertex in Vr a 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.

AB - Given a connected graph G = (V, E), two distinct base vertices u 1 ,u2 ∈ Vr, a set Vr ⊆ V of r special vertices and two natural numbers r1,r2 such that r1 + r2 = r, we wish to find a partition V 1, V2 of the vertex set V such that u1 ∈, V1, u2 ∈ V2, Vi induces a connected subgraph Gi of G for each i, 1 ≤ i ≤ 2, V1 contains r1 vertices from Vr and V2 contains r2 vertices from Vr. We call a vertex in Vr a 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.

UR - http://www.scopus.com/inward/record.url?scp=46249093972&partnerID=8YFLogxK

U2 - 10.1109/ICECE.2006.355633

DO - 10.1109/ICECE.2006.355633

M3 - Conference contribution

SN - 9843238141

SN - 9789843238146

T3 - Proceedings of 4th International Conference on Electrical and Computer Engineering, ICECE 2006

SP - 308

EP - 311

BT - Proceedings of 4th International Conference on Electrical and Computer Engineering, ICECE 2006

PB - IEEE Computer Society

Y2 - 19 December 2006 through 21 December 2006

ER -