树上的限制性node multicut问题

J4 ›› 2014, Vol. 13 ›› Issue (12): 21-25.

树上的限制性node multicut问题

昭通学院数学与统计学院，云南昭通 657000

收稿日期:2014-05-07 出版日期:2014-12-15 发布日期:2014-12-15
作者简介:杨惠娟，助教，主要从事图论与组合优化研究.

Restricted Node Multicut Problem in Trees

College of Mathematics and Statistics, Zhaotong College, Zhaotong, Yunnan 657000, China

Received:2014-05-07 Online:2014-12-15 Published:2014-12-15

摘要/Abstract

摘要：

割集问题在图论和组合优化中占有重要地位，限制性node multicut问题是割集问题的一类比较重要的推广问题。树上
的限制性node multicut问题是值得研究的一个问题。首先说明此问题是NP 难的，其次用线性规划理论中的互补松弛条件设
计了一个近似值2且时间复杂度为O(max{kn,n logn}) 的算法。并进一步说明了通过算法得到的解具有半整数的性质。

关键词: 限制性node multicut , 近似算法, 互补松弛条件

Abstract:

The problem of cut set holds an important position in graph theory and combinatorial optimization and restricted node
multicut is a significant problem in cut set. And restricted node multicut problem in trees is worth studying. The paper first explains
that the node multicut problem is hard, then designs an algorithm with the approximate value of 2 and time complexity of by applying
complementary slackness conditions in linear programming theory, and finally further explains the solution from the algorithm is a halfinteger.

Key words: restricted node multicut, approximation algorithm, complementary slackness conditions

中图分类号:

O157.5

杨惠娟. 树上的限制性node multicut问题[J]. J4, 2014, 13(12): 21-25.

YANG Huijuan. Restricted Node Multicut Problem in Trees[J]. J4, 2014, 13(12): 21-25.

参考文献

〔1〕拉文德拉K. 阿胡亚，托马斯L. 马南提，詹姆斯B. 沃琳，
等.网络流理论算法与应用〔M〕. 北京: 机械工业出版社，
2005:207-240.
〔2〕刘振宏，蔡茂诚. 组合最优化:计算机算法和复杂
性〔M〕. 北京: 清华大学出版社，1988:248-269.
〔3〕STEFAN K，MARCIN P，MICHAL P.Fixed-parameter trac?
tability of multicut in directed acyclic graphs〔J〕.Computer
Science，2012（7391）:581-593.
〔4〕JORGEN B J，ANDERS Y.The complexity of multicut and
mixed multicut problems in （di）graphs〔J〕. Theoretical
Computer Science，2014（520）:87-96.
〔5〕HU T C. Multicommodity network flows〔J〕.Oper Res，1963
（9）:898-900.
〔6〕DAHLHAUS E，JOHNSON D S，PAPADIMITRIOU C H，
et al. The complexity of multiterminal cuts〔J〕.SIAM J Com?
put，1994，23（4）:864-894.
〔7〕CHAWLA S，KRAUTHGAMER R，KUMAR R，et al. On
the hardness of approximating multicut and sparsestcut
〔J〕. Computational Complexity，2006，15（2）:94-114 .
〔8〕GARG N，VAZIRANI V，YANNAKAKIS M. Primal-dual
approximation algorithms for integral flow and multicut in
trees〔J〕.Algorithmica，1997（18）:3-20.
〔9〕Costa M C，Letocart L，Roupin F. A greedy algorithm for
multicut and integral multiflow in rooted trees〔J〕.Opera?
tions Research Letters，2003（31）: 21-27.
〔10〕CALINESCU G，FERNANDES C G，REED B. Multicuts
in unweighted graphs and digraphs with bounded degree
and bounded tree-width〔J〕. Journal of Algorithms，2003
（48）:333-359.
〔11〕GUO J，HUFFNER F，KENAR E，et al.Complexity and
exact algorithms for vertex multicut in interval and bound?
ed treewidth graphs〔J〕.European Journal of Operational
Research，2008（186）:542-553.
〔12〕CHARIS P.Restricted vertex multicut on permutation
graphs〔J〕.Discrete Applied Mathematics，2012（160）:
1791-1797.
〔13〕JULIAN M.Lagrangian relaxation and partial cover（ex?
tended abstract）〔J〕.Theoretical Aspects of Computer Sci?
ence，2008（25）:539-550.
〔14〕ZHANG P，ZHU D，LUAN J F.An approximation algo?
rithm for the Generalized k-Multicut problem〔J〕.Discrete
Applied Mathematics，2012（160）:1240-1247.