On resource bipartitioning problem

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

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

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
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
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. IEEE Computer Society, 2006. 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 = "2006",
month = "1",
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",
publisher = "IEEE Computer Society",
pages = "308--311",
booktitle = "Proceedings of 4th International Conference on Electrical and Computer Engineering, ICECE 2006",

}

Shams, Z, Ferdous, S, Sultana, KZ & Rahman, MS 2006, 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, IEEE Computer Society, 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. IEEE Computer Society, 2006. p. 308-311 4178469 (Proceedings of 4th International Conference on Electrical and Computer Engineering, ICECE 2006).

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

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

AN - SCOPUS:46249093972

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

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. IEEE Computer Society. 2006. p. 308-311. 4178469. (Proceedings of 4th International Conference on Electrical and Computer Engineering, ICECE 2006). https://doi.org/10.1109/ICECE.2006.355633