Series-Parallel图上最小权顶点覆盖3-路问题的有效算法

详细信息    查看全文 | 推荐本文 |

英文篇名：An efficient algorithm for the minimum weight vertex cover 3-path problem on Series-Parallel graphs 作者：张文杰 ; 涂建华 英文作者：ZHANG WenJie;TU JianHua;Faculty of Science, Beijing University of Chemical Technology; 关键词：Series-Parallel图 ; 顶点覆盖k-路问题 ; 有效算法 ; 动态规划 英文关键词：Series-Parallel graphs;;vertex cover k-path problem;;efficient algorithms;;dynamic programming 中文刊名：BJHY 英文刊名：Journal of Beijing University of Chemical Technology(Natural Science Edition) 机构：北京化工大学理学院; 出版日期：2019-01-20 出版单位：北京化工大学学报(自然科学版) 年：2019 期：v.46 语种：中文; 页：BJHY201901019 页数：5 CN：01 ISSN：11-4755/TQ 分类号：126-130

摘要

研究了Series-Parallel图上的顶点覆盖3-路问题,利用动态规划思想,给出一个能在多项式时间内完成的有效算法,该算法的运行时间为O(|V|)。
        Given a vertex-weighted graph G=(V, E) and a positive integer k≥2, the minimum weight vertex cover k-path problem(MWVCP_k) asks for a vertex subset F?V with minimum weight such that every path of order k contains at least one vertex from F. For any integer k≥2, MWVCP_k on general graphs is NP-hard. In this paper, we study MWVCP_3 on Series-Parallel graphs and present a dynamic programming algorithm with runtime O(|V|).

引文

[1] NOVOTNY M. Design and analysis of a generalized canvas protocol[C]//WISTP 2010: Security and Privacy of Pervasive Systems and Smart Devices. Passau, 2010: 106- 121.
    [2] TU J H, ZHOU W L. A primal-dual approximation algorithm for the vertex cover P3 problem[J]. Theoretical Computer Science, 2011, 412(50): 7044- 7048.
    [3] KARDO? F, KATRENIC J, SCHIERMEYER I. On computing the minimum 3-path vertex cover and dissociation number of graphs[J]. Theoretical Computer Science, 2011, 412(50): 7009- 7017.
    [4] BRE?AR B, KRIVO?-BELLU? R, SEMANI?IN G, et al. On the weighted k-path vertex cover problem[J]. Discrete Applied Mathematics, 2014, 177: 14- 18.
    [5] TU J H, YANG F M. The vertex cover P3 problem in cubic graphs[J]. Information Processing Letters, 2013, 113: 481- 485.
    [6] LI Y C, TU J H. A 2-approximation algorithm for the vertex cover P4 problem in cubic graphs[J]. International Journal of Applied Mathematics and Computer Science, 2014, 91(10): 2103- 2108.
    [7] DEVI N S, MANE A C, MISHRA S. Computational complexity of minimum P4 vertex cover problem for regular and K1, 4-free graphs[J]. Discrete Applied Mathematics, 2015, 184: 114- 121.
    [8] DUFFIN R J. Topology of series-parallel networks[J]. Journal of Mathematical Analysis and Applications, 1965, 10(2): 303- 318.
    [9] NAGY M, AKL S G. Real-time minimum vertex cover for two-terminal Series-Parallel graphs[J]. International Journal of High Performance Computing & Networking, 2000, 4(5): 347- 356.