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/9931

Title: A linear-time algorithm for k-partitioning doughnut graphs
???metadata.dc.creator???: Karim, Rezaul
Nahiduzzaman, Kaiser
Rahman, Saidur
Keywords: Planar graph
Doughnut graph
Graph partitioning
Grafo planar
Gráfico em donut
Partição de grafos
Publisher: Editora da UFLA
???metadata.dc.date???: 1-Mar-2009
Citation: KARIM, R.; NAHIDUZZAMAN, K.; RAHMAN, S. A linear-time algorithm for k-partitioning doughnut graphs. INFOCOMP: Journal of Computer Science, Lavras, v. 8, n. 1, p. 8-13, Mar. 2009.
Abstract: Given a graph G = (V,E), k natural numbers n1, n2, ..., nk such that Pk i=1 ni = |V |, we wish to find a partition V1, V2, ..., Vk of the vertex set V such that |Vi| = ni and Vi induces a connected subgraph of G for each i, 1 i k. Such a partition is called a k-partition of G. The problem of finding a k-partition of a graph G is NP-hard in general. It is known that every k-connected graph has a k-partition. But there is no polynomial time algorithm for finding a k-partition of a k-connected graph. In this paper we give a simple linear-time algorithm for finding a k-partition of a “doughnut graph” G.
Other Identifiers: http://www.dcc.ufla.br/infocomp/index.php/INFOCOMP/article/view/245
???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