A Linear-Time Algorithm for k-Partitioning Doughnut Graphs
Main Article Content
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.
Article Details
How to Cite
Karim, M. R., Nahiduzzaman, K. M., & Rahman, M. S. (2009). A Linear-Time Algorithm for k-Partitioning Doughnut Graphs. INFOCOMP Journal of Computer Science, 8(1), 8–13. Retrieved from https://infocomp.dcc.ufla.br/index.php/infocomp/article/view/245
Section
Articles
Upon receipt of accepted manuscripts, authors will be invited to complete a copyright license to publish the paper. At least the corresponding author must send the copyright form signed for publication. It is a condition of publication that authors grant an exclusive licence to the the INFOCOMP Journal of Computer Science. This ensures that requests from third parties to reproduce articles are handled efficiently and consistently and will also allow the article to be as widely disseminated as possible. In assigning the copyright license, authors may use their own material in other publications and ensure that the INFOCOMP Journal of Computer Science is acknowledged as the original publication place.