无向图中边不相交Min-Min问题的复杂度

doi:10.7523/j.issn.2095-6134.2012.4.018

中国科学院大学学报 ›› 2012, Vol. 29 ›› Issue (4): 549-554.DOI: 10.7523/j.issn.2095-6134.2012.4.018

无向图中边不相交Min-Min问题的复杂度

郭龙坤, 沈鸿

中国科学技术大学计算机学院, 合肥 230026

收稿日期:2011-04-02 修回日期:2011-05-20 发布日期:2012-07-15
通讯作者: 沈鸿
基金资助:
Supported by NSFC (622307), the "100 Talents" Project of Chinese Academy of Sciences, and China Scholarship Council's State Scholarship Fund (2009634119)

Hardness of the edge-disjoint Min-Min problem in undirected graphs

GUO Long-Kun, SHEN Hong

School of Computer Science, University of Science and Technology of China, Hefei 230026, China

Received:2011-04-02 Revised:2011-05-20 Published:2012-07-15

摘要/Abstract

摘要： Bhatia等指出,Xu等对无向图中的边不相交Min-Min问题的NP-完全性证明并不成立. 我们首先用一个反例指出Bhatia等对Xu等的NP-完全性证明的修正依然存在错误. 基于一个从MAX-2SAT的归约,我们给出了一个无向图中边不相交Min-Min问题的NP-完全性的正确证明.

关键词: Min-Min问题, NP-完全, 不相交路径对, MAX-2SAT问题

Abstract: We show incorrectness of the NP-completeness proof of Bhatia et al. for the edge-disjoint Min-Min problem in undirected graphs, by giving a counter example that is an unsatisfiable 3SAT instance but was classified satisfiable in the proof of Bhatia et al. We then give a proof of NP-completeness of the edge-disjoint Min-Min problem in undirected graphs, based on a reduction from the MAX-2SAT problem.

Key words: Min-Min problem, NP-completeness, disjoint path pair, MAX-2SAT

中图分类号:

TP301.5

郭龙坤, 沈鸿. 无向图中边不相交Min-Min问题的复杂度[J]. 中国科学院大学学报, 2012, 29(4): 549-554.

GUO Long-Kun, SHEN Hong. Hardness of the edge-disjoint Min-Min problem in undirected graphs[J]. , 2012, 29(4): 549-554.

参考文献

[1] Xu D, Chen Y, Xiong Y, et al. On the complexity of and algorithms for finding the shortest path with a disjoint counterpart[J]. IEEE/ACM Transactions on Networking, 2006, 14(1):147-158.
[2] Bhatia R, Kodialam M, Lakshman T. Finding disjoint paths with related path costs[J]. Journal of Combinatorial Optimization, 2006, 12(1): 83-96.
[3] Bouillet E, Labourdette J, Ramamurthy R, et al. Lightpath re-optimization in mesh optical networks[J]. IEEE/ACM Transactions on Networking (TON), 2005, 13(2): 437-447.
[4] Li C, McCormick S, Simchi-Levi D. Finding disjoint paths with different path-costs: Complexity and algorithms[J]. Networks, 1992, 22(7): 653-667.
[5] Zheng S, Yang B, Yang M, et al. Finding minimum-cost paths with minimum sharability //26th IEEE International Conference on Computer Communications. 2007: 1532-1540.
[6] Seymour P. Disjoint paths in graphs[J]. Discrete Mathematics, 2006, 306(10): 979-991.
[7] Liu G, Ramakrishnan K. A* Prune: an algorithm for finding K shortest paths subject tomultiple constraints //IEEE INFOCOM 2001.Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies. 2001, 2: 743-749.
[8] Shiloach Y. A polynomial solution to the undirected two paths problem[J]. Journal of the ACM (JACM), 1980, 27(3):445-456.
[9] Suurballe J. Disjoint paths in a network[J]. Networks,1974, 4(2): 125-145.
[10] Suurballe J, Tarjan R. A quick method for finding shortest pairs of disjoint paths[J]. Networks, 1984, 14(2): 325-336.
[11] Bhandari R. Optimal physical diversity algorithms and survivable networks //Proceedings of Second IEEE Symposium on Computers and Communications. 1997: 433-441.
[12] Li C, McCormick T, Simich-Lev D. The complexity of finding two disjoint paths with min-max objective function[J]. Discrete Applied Mathematics, 1989, 26(1): 105-115.
[13] Sen A. Survivability of lightwave networks-path lengths in WDM protection scheme[J]. Journal of High Speed Networks, 2001, 10(4): 303-315.
[14] Holst H, Pina J. Length-bounded disjoint paths in planar graphs[J]. Discrete Applied Mathematics, 2002, 120(1): 251-261.
[15] Guo L, Shen H. Hardness of finding two edge-disjoint Min-Min paths in digraphs //Lecture Notes in Computer Science 6681.Springer, 2011: 301-308.
[16] Schrijver A. Finding k disjoint paths in a directed planar graph[J]. SIAM J Computing, 1994, 23(4): 780-788.
[17] Garey M, Johnson L. Some simplified NP-complete graph problems[J]. Theoretical Computer Science, 1976, 1(3): 237-267.

无向图中边不相交Min-Min问题的复杂度

Hardness of the edge-disjoint Min-Min problem in undirected graphs

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价

访问统计

联系我们