期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

几类特殊平面图的圈包装问题 被引量：1

The cycle packing problem on some special classes of planar graphs
下载PDF
导出
摘要 给定一个无向连通图G ,圈包装问题就是求G的边不相交圈的最大数目 .此问题在一般图下是APX困难问题 ,在平面图下是NP困难问题 .主要证明了在几类特殊的平面图下多项式时间可得到最优解 .主要考虑外平面图 ,系列平行图和平面欧拉图这三类特殊的平面图 . In the cycle packing problem, given an undirected connected graph G, it is required to find the maximum number of pairwise edge disjoint cycles in G. It is known that the problem is APX-hard for general graphs and NP-hard for planar graphs. In this paper we prove that the problem is polynomial solvable on several special classes of graphs, such as outerplanar graphs, series-parallel graphs and Eulerian planar graphs.
作者 张少强 王继强 李曙光
机构地区 山东大学数学与系统科学学院 山东财政学院文理学院 烟台大学数学与信息科学系
出处 《山东大学学报（理学版）》 CAS CSCD 北大核心 2004年第1期1-4,共4页 Journal of Shandong University(Natural Science)
基金 国家自然科学基金资助项目 ( 1 0 2 71 0 6 5 )
关键词 包装 圈 多项式时间算法 外平面图 系列平行图 欧拉图 packing cycles polynomial algorithm outerplanar graphs series-parallel graphs Eulerian
分类号 O157 [理学—基础数学] TP301 [自动化与计算机技术—计算机系统结构]
  • 相关文献

参考文献7

  • 1[1]A A Ageev. On Finding the Maximum Number of Disjoint Cuts in Seymour Graphs [A]. Proceedings of the 7th European Symposium on Algorithms (ESA' 99), Lecture Notes in Computer Science, 1643[C]. Berlin Springer, 1999. 490～497.
  • 2[2]J A Bondy, U S R Murty. Graph Theory with Applications[M]. London, the Macmillan Press, 1976.
  • 3[3]A Caprara. Sorting Permutations by Reversals and Eulerian Cycle Decompositions[J]. SIAM J on Discrete Mathematics, 1999, 12: 91～110.
  • 4[4]A Caprara, A Panconesi, R Rizzi. Packing Cycles in Undirected Graphs[J]. J Algorithms, 2003, 48(1): 239～256.
  • 5[5]A Frank. Conservative Weightings and Ear-Decompositions of Graphs[J]. Combinatorica, 1993, 13: 65～81.
  • 6[6]M C Golumbic. Algorithmic Graph Theory and Perfect Graphs[M]. New York: Academic Press, 1980.
  • 7[7]P D Seymour. The Matroids with the Max-Flow Min-Cut Property[J]. J Comb Theory, B23, 1977: 189～222.

同被引文献6

  • 1Padberg M W.Covering, packing and knapsack problems[J].An-nals of Discrete Mathematics, 1979,4:265-287.
  • 2Garey M R, Johnson D S.Computers and intractability:a guide to NP-completeness[M].San Francisco;Freeman, 1979.
  • 3Hassin R, Rubinstein S.Robust matchings, maximum clustering and maximum capacitated medians[C]//Lecture Notes in Computer Sci-ence, 2000,1851 : 251-258.
  • 4Kowa|ik L, Mucha M.Deterministic 7/8-approximation lbr met-ric max-TSP[C]//Proceedings of I lth International Workshop on Approximation Algorithms for Combinatorial Optimization Prob-lems(APPROX) ,2008,5171 : 132-145.
  • 5Hassin R, Rubinstein S.A 7/8-approximation approximations for metric max-TSP[J].lnformation Processing Letters, 2002,81 : 247-251.
  • 6Hassin R, Rubinstein S.An approximation algorithm for maximum packing of 3-edge paths[J].lnformation Processing Letter, 1997, 63(5) :63-67.

引证文献1

山东大学学报（理学版）
2004年 第1期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部