On Packing and Coloring Hyperedges in a Cycle
For a hypergraph and k different colors, we study the problem of packing and coloring some hyperedges of the hypergraph as paths in a cycle such that the total profit of the chosen hyperedges are maximized, here each link ej on the cycle is used at most cj times, each hyperedge hi has a profit pi and any two paths, each spanning all vertices of its corresponding hyperedge, must receive different colors if they share a link. This new problem arises in optical communication networks and it is called the Maximum Profits of Packing and Coloring Hyperedges in a Cycle problem (MPPCHC). In this paper, we prove that the MPPCHC problem is NP-hard and present a 2-approximation algorithm. For the special case, where each hyperedge has the same profit and each capacity cj is k, we propose a 3/2approximation algorithm to handle the problem.
Minimum-cost flow hyperedge path coloring approzimation algorithm
Jianping Li Kang Li Ken C.K. Law Hao Zhao
Department of Mathematics, Yunnan University Kunming 650091, P.R. China Department of Computer Scien School of Information Science and Engineering, Shandong University Shandong 250100, P.R. China Department of Computer Science, City University of Hong Kong Tat Chee Avenue, Kowloon, Hong Kong, P.
国际会议
The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)
昆明
英文
220-229
2005-08-01（万方平台首次上网日期，不代表论文的发表时间）