On resource bipartitioning problem

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

2 Citations (Scopus)

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
Pages308-311
Number of pages4
DOIs
StatePublished - 1 Dec 2007
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. (2007). 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). https://doi.org/10.1109/ICECE.2006.355633
Shams, Zalia ; Ferdous, Shahina ; Sultana, Kazi Zakia ; Rahman, Md Saidur. / On resource bipartitioning problem. Proceedings of 4th International Conference on Electrical and Computer Engineering, ICECE 2006. 2007. pp. 308-311 (Proceedings of 4th International Conference on Electrical and Computer Engineering, ICECE 2006).
@inproceedings{471d036dccb54f51a6a4998eb429611b,
title = "On resource bipartitioning problem",
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.",
author = "Zalia Shams and Shahina Ferdous and Sultana, {Kazi Zakia} and Rahman, {Md Saidur}",
year = "2007",
month = "12",
day = "1",
doi = "10.1109/ICECE.2006.355633",
language = "English",
isbn = "9843238141",
series = "Proceedings of 4th International Conference on Electrical and Computer Engineering, ICECE 2006",
pages = "308--311",
booktitle = "Proceedings of 4th International Conference on Electrical and Computer Engineering, ICECE 2006",

}

Shams, Z, Ferdous, S, Sultana, KZ & Rahman, MS 2007, On resource bipartitioning problem. in 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.

Proceedings of 4th International Conference on Electrical and Computer Engineering, ICECE 2006. 2007. p. 308-311 4178469 (Proceedings of 4th International Conference on Electrical and Computer Engineering, ICECE 2006).

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-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 -

Shams Z, Ferdous S, Sultana KZ, Rahman MS. On resource bipartitioning problem. In Proceedings of 4th International Conference on Electrical and Computer Engineering, ICECE 2006. 2007. p. 308-311. 4178469. (Proceedings of 4th International Conference on Electrical and Computer Engineering, ICECE 2006). https://doi.org/10.1109/ICECE.2006.355633