### Abstract

Given a connected graph G = (V, E), two distinct base vertices u _{1} ,u_{2} ∈ V_{r}, a set V_{r} ⊆ V of r special vertices and two natural numbers r_{1},r_{2} such that r_{1} + r_{2} = r, we wish to find a partition V _{1}, V_{2} of the vertex set V such that u_{1} ∈, V_{1}, u_{2} ∈ V_{2}, V_{i} induces a connected subgraph G_{i} of G for each i, 1 ≤ i ≤ 2, V_{1} contains r_{1} vertices from V_{r} and V_{2} contains r_{2} vertices from V_{r}. We call a vertex in V_{r} 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.

Original language | English |
---|---|

Title of host publication | Proceedings of 4th International Conference on Electrical and Computer Engineering, ICECE 2006 |

Pages | 308-311 |

Number of pages | 4 |

DOIs | |

State | Published - 1 Dec 2007 |

Event | 4th International Conference on Electrical and Computer Engineering, ICECE 2006 - Dhaka, Bangladesh Duration: 19 Dec 2006 → 21 Dec 2006 |

### Publication series

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

### Conference

Conference | 4th International Conference on Electrical and Computer Engineering, ICECE 2006 |
---|---|

Country | Bangladesh |

City | Dhaka |

Period | 19/12/06 → 21/12/06 |

### Cite this

*Proceedings of 4th International Conference on Electrical and Computer Engineering, ICECE 2006*(pp. 308-311). [4178469] (Proceedings of 4th International Conference on Electrical and Computer Engineering, ICECE 2006). https://doi.org/10.1109/ICECE.2006.355633

}

*Proceedings of 4th International Conference on Electrical and Computer Engineering, ICECE 2006.*, 4178469, Proceedings of 4th International Conference on Electrical and Computer Engineering, ICECE 2006, pp. 308-311, 4th International Conference on Electrical and Computer Engineering, ICECE 2006, Dhaka, Bangladesh, 19/12/06. https://doi.org/10.1109/ICECE.2006.355633

**On resource bipartitioning problem.** / Shams, Zalia; Ferdous, Shahina; Sultana, Kazi Zakia; Rahman, Md Saidur.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

TY - GEN

T1 - On resource bipartitioning problem

AU - Shams, Zalia

AU - Ferdous, Shahina

AU - Sultana, Kazi Zakia

AU - Rahman, Md Saidur

PY - 2007/12/1

Y1 - 2007/12/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

ER -