RI UFLA (Universidade Federal de Lavras) >
Revistas UFLA >
Please use this identifier to cite or link to this item:
|Title: ||A linear-time algorithm for k-partitioning doughnut graphs|
|???metadata.dc.creator???: ||Karim, Rezaul|
|Keywords: ||Planar graph|
Gráfico em donut
Partição de grafos
|Publisher: ||Editora da UFLA|
|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|
|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.