On resource bipartitioning problem

Zalia Shams, Shahina Ferdous, Kazi Zakia Sultana, Md Saidur Rahman

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publicationProceedings of 4th International Conference on Electrical and Computer Engineering, ICECE 2006
PublisherIEEE Computer Society
Pages308-311
Number of pages4
ISBN (Print)9843238141, 9789843238146
DOIs
StatePublished - 1 Jan 2006
Event4th International Conference on Electrical and Computer Engineering, ICECE 2006 - Dhaka, Bangladesh
Duration: 19 Dec 200621 Dec 2006

Publication series

NameProceedings of 4th International Conference on Electrical and Computer Engineering, ICECE 2006

Conference

Conference4th International Conference on Electrical and Computer Engineering, ICECE 2006
CountryBangladesh
CityDhaka
Period19/12/0621/12/06

Cite this

Shams, Z., Ferdous, S., Sultana, K. Z., & Rahman, M. S. (2006). On resource bipartitioning problem. In 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