An Optimal Algorithm for Tree Geometrical k-cut Problem

被引：0

作者：

Cho, Sang-Young ^{[1
]}

Kim, Hee-Chul ^{[1
]}

机构：

[1] Hankuk Univ Foreign Studies, Dept Comp Sci & Engn, Wangsan Mohyeon, Yongin Kyeonggi, South Korea

来源：

MACMESE 2008: PROCEEDINGS OF THE 10TH WSEAS INTERNATIONAL CONFERENCE ON MATHEMATICAL AND COMPUTATIONAL METHODS IN SCIENCE AND ENGINEERING, PTS I AND II | 2008年

关键词：

complexity; k-cut; tree; max-flow; min-cut; multi-terminal graph; partitioning; topology;

D O I：

暂无

中图分类号：

T [工业技术];

学科分类号：

08 ;

摘要：

Geometrical k-cut problem has numerous applications, particularly in clusterin g-related setups such as task assignment and VLSI cell placement. This problem is NP-hard in general. We propose an optimal algorithm to solve the problem for tree topology graphs in polynomial time. The time complexity of the algorithm is O(kn(3)), where n is the number of nodes in a k-terminal graph, with the Goldberg-Tarjan's network flow algorithm.

引用

页码：280 / +

页数：2

共 6 条

[1]

[Anonymous], 1988, P 29 ANN IEEE S FDN

[2] THEORETICAL IMPROVEMENTS IN ALGORITHMIC EFFICIENCY FOR NETWORK FLOW PROBLEMS [J].