On resource bipartitioning problem

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

doi:10.1109/ICECE.2006.355633

On resource bipartitioning problem

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

Computer Science

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

2 Scopus citations

Abstract

Given a connected graph G = (V, E), two distinct base vertices u ₁ ,u₂ ∈ V_r, a set V_r ⊆ V of r special vertices and two natural numbers r₁,r₂ such that r₁ + r₂ = r, we wish to find a partition V ₁, V₂ of the vertex set V such that u₁ ∈, V₁, u₂ ∈ V₂, V_i induces a connected subgraph G_i of G for each i, 1 ≤ i ≤ 2, V₁ contains r₁ vertices from V_r and V₂ contains r₂ 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	https://doi.org/10.1109/ICECE.2006.355633
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/Territory	Bangladesh
City	Dhaka
Period	19/12/06 → 21/12/06

Access to Document

10.1109/ICECE.2006.355633

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

@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 = jan,

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",

note = "4th International Conference on Electrical and Computer Engineering, ICECE 2006 ; Conference date: 19-12-2006 Through 21-12-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 et al.
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 proceeding › Conference contribution › peer-review

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

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

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

Y2 - 19 December 2006 through 21 December 2006

ER -

On resource bipartitioning problem

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this