### 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 |

Publisher | IEEE Computer Society |

Pages | 308-311 |

Number of pages | 4 |

ISBN (Print) | 9843238141, 9789843238146 |

DOIs | |

State | Published - 1 Jan 2006 |

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). IEEE Computer Society. https://doi.org/10.1109/ICECE.2006.355633