A Linear Algorithm for Resource Tripartitioning Triconnected Planar Graphs

Main Article Content

Tanveer Awal MD. Saidur Rahman

Abstract

Given a connected graph G = (V,E), a set Vr ⊆ V of r special vertices, three distinct base vertices u1, u2, u3 ∈ V and three natural numbers r1, r2, r3 such that r1 + r2 + r3 = r, we wish to find a partition V1, V2, V3 of V such that Vi contains ui and ri vertices from Vr, and Vi induces a connected subgraph of G for each i, 1 ≤ i ≤ 3. We call a vertex in Vr a resource vertex and the problem above of partitioning vertices of G as the resource 3-partitioning problem. In this paper, we give a linear-time algorithm for finding a resource tripartition of a 3-connected planar graph G. Our algortihm is based on a nonseparating ear decomposition of G and st-numbering of G. We also present a linear algorithm to
find a nonseparating ear decomposition of a 3-connected planar graph. This algorithm has bounds on ear-length and number of ears.

Article Details

How to Cite
AWAL, Tanveer; RAHMAN, MD. Saidur. A Linear Algorithm for Resource Tripartitioning Triconnected Planar Graphs. INFOCOMP, [S.l.], v. 9, n. 2, p. 39-48, june 2010. ISSN 1982-3363. Available at: <http://www.dcc.ufla.br/infocomp/index.php/INFOCOMP/article/view/301>. Date accessed: 22 apr. 2019.
Keywords
Algorithm, Nonseparating ear decomposition, Planar graph, Resource trip artitioning, Resource bipartitioning, st-numbering, Triconnected graph
Section
Articles