Buscar

 

RI UFLA (Universidade Federal de Lavras) >
Revistas UFLA >
Infocomp >

Please use this identifier to cite or link to this item: http://repositorio.ufla.br/jspui/handle/1/9937

Title: A linear algorithm for resource tripartitioning triconnected planar graphs
???metadata.dc.creator???: Awal, Tanveer
Rahman, MD. Saidur
Keywords: Algorithm
Nonseparating ear decomposition
Planar graph
Resource tripartitioning
Resource bipartitioning
St-numbering
Triconnected graph
Algoritmo
Grafo planar
Tripartição de recursos
Bipartição de recursos
Orientação bipolar
Gráfico triconectado
Publisher: Editora da UFLA
???metadata.dc.date???: 1-Jun-2010
Citation: AWAL, T.; RAHMAN, M. S. A linear algorithm for resource tripartitioning triconnected planar graphs. INFOCOMP: Journal of Computer Science, Lavras, v. 9, n. 2, p. 39-48, June 2010.
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 tofind a nonseparating ear decomposition of a 3-connected planar graph. This algorithm has bounds on ear-length and number of ears.
Other Identifiers: http://www.dcc.ufla.br/infocomp/index.php/INFOCOMP/article/view/301
???metadata.dc.language???: eng
Appears in Collections:Infocomp

Files in This Item:

There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


View Statistics

 


DSpace Software Copyright © 2002-2010  Duraspace - Feedback