Approximation algorithms for minimum (weight) connected -path vertex cover

详细信息    查看全文

• 作者：Xiaosong Li^a ; Zhao Zhang^b ; ^{hxhzz@sina.com" class="auth_mail" title="E-mail the corresponding author} ; Xiaohui Huang^b
• 关键词：Connected kk-path vertex cover ; Weight ; Tree ; Girth ; Approximation algorithm
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：31 May 2016
• 年：2016
• 卷：205
• 期：Complete
• 页码：101-108
• 全文大小：525 K

文摘

A vertex subset an id="mmlsi19" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005739&_mathId=si19.gif&_user=111111111&_pii=S0166218X15005739&_rdoc=1&_issn=0166218X&md5=d6b244d33542bae1c09a2439b79cb639" title="Click to view the MathML source">Can>an class="mathContainer hidden">an class="mathCode">ath altimg="si19.gif" overflow="scroll">Cath>an>an>an> of a connected graph an id="mmlsi4" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005739&_mathId=si4.gif&_user=111111111&_pii=S0166218X15005739&_rdoc=1&_issn=0166218X&md5=bf422dd206facda2b48454477519b08e" title="Click to view the MathML source">Gan>an class="mathContainer hidden">an class="mathCode">ath altimg="si4.gif" overflow="scroll">Gath>an>an>an> is called a connected an id="mmlsi17" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005739&_mathId=si17.gif&_user=111111111&_pii=S0166218X15005739&_rdoc=1&_issn=0166218X&md5=8941d82c12d175b92d07c31d6d815591" title="Click to view the MathML source">kan>an class="mathContainer hidden">an class="mathCode">ath altimg="si17.gif" overflow="scroll">kath>an>an>an>-path vertex cover (an id="mmlsi22" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005739&_mathId=si22.gif&_user=111111111&_pii=S0166218X15005739&_rdoc=1&_issn=0166218X&md5=687122783f5c884f2b88c16d98745fed" title="Click to view the MathML source">CVCP_kan>an class="mathContainer hidden">an class="mathCode">ath altimg="si22.gif" overflow="scroll">CVCPkath>an>an>an>) if every path on an id="mmlsi17" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005739&_mathId=si17.gif&_user=111111111&_pii=S0166218X15005739&_rdoc=1&_issn=0166218X&md5=8941d82c12d175b92d07c31d6d815591" title="Click to view the MathML source">kan>an class="mathContainer hidden">an class="mathCode">ath altimg="si17.gif" overflow="scroll">kath>an>an>an> vertices contains at least one vertex from an id="mmlsi19" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005739&_mathId=si19.gif&_user=111111111&_pii=S0166218X15005739&_rdoc=1&_issn=0166218X&md5=d6b244d33542bae1c09a2439b79cb639" title="Click to view the MathML source">Can>an class="mathContainer hidden">an class="mathCode">ath altimg="si19.gif" overflow="scroll">Cath>an>an>an>, and the subgraph of an id="mmlsi4" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005739&_mathId=si4.gif&_user=111111111&_pii=S0166218X15005739&_rdoc=1&_issn=0166218X&md5=bf422dd206facda2b48454477519b08e" title="Click to view the MathML source">Gan>an class="mathContainer hidden">an class="mathCode">ath altimg="si4.gif" overflow="scroll">Gath>an>an>an> induced by an id="mmlsi19" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005739&_mathId=si19.gif&_user=111111111&_pii=S0166218X15005739&_rdoc=1&_issn=0166218X&md5=d6b244d33542bae1c09a2439b79cb639" title="Click to view the MathML source">Can>an class="mathContainer hidden">an class="mathCode">ath altimg="si19.gif" overflow="scroll">Cath>an>an>an> is connected. This concept originated in the field of security and supervisory control. This paper studies the minimum (weight) an id="mmlsi22" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005739&_mathId=si22.gif&_user=111111111&_pii=S0166218X15005739&_rdoc=1&_issn=0166218X&md5=687122783f5c884f2b88c16d98745fed" title="Click to view the MathML source">CVCP_kan>an class="mathContainer hidden">an class="mathCode">ath altimg="si22.gif" overflow="scroll">CVCPkath>an>an>an> problem. We first show that the minimum weight an id="mmlsi22" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005739&_mathId=si22.gif&_user=111111111&_pii=S0166218X15005739&_rdoc=1&_issn=0166218X&md5=687122783f5c884f2b88c16d98745fed" title="Click to view the MathML source">CVCP_kan>an class="mathContainer hidden">an class="mathCode">ath altimg="si22.gif" overflow="scroll">CVCPkath>an>an>an> problem can be solved in time an id="mmlsi29" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005739&_mathId=si29.gif&_user=111111111&_pii=S0166218X15005739&_rdoc=1&_issn=0166218X&md5=6babd945612d7845fe497dafb8d3adf4" title="Click to view the MathML source">O(n)an>an class="mathContainer hidden">an class="mathCode">ath altimg="si29.gif" overflow="scroll">O(n)ath>an>an>an> when the graph is a tree, and can be solved in time an id="mmlsi30" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005739&_mathId=si30.gif&_user=111111111&_pii=S0166218X15005739&_rdoc=1&_issn=0166218X&md5=2e03558610b00d9c42dc799b6f9f803f" title="Click to view the MathML source">O(rn)an>an class="mathContainer hidden">an class="mathCode">ath altimg="si30.gif" overflow="scroll">O(rn)ath>an>an>an> when the graph is a uni-cyclic graph whose unique cycle has length an id="mmlsi31" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005739&_mathId=si31.gif&_user=111111111&_pii=S0166218X15005739&_rdoc=1&_issn=0166218X&md5=d24829411ce1328326d7555e6dbb8f8a" title="Click to view the MathML source">ran>an class="mathContainer hidden">an class="mathCode">ath altimg="si31.gif" overflow="scroll">rath>an>an>an>, where an id="mmlsi32" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005739&_mathId=si32.gif&_user=111111111&_pii=S0166218X15005739&_rdoc=1&_issn=0166218X&md5=a5f07d00c9da59cb555a63dc6d209c53" title="Click to view the MathML source">nan>an class="mathContainer hidden">an class="mathCode">ath altimg="si32.gif" overflow="scroll">nath>an>an>an> is the number of vertices. Making use of the algorithm on trees, we present a an id="mmlsi17" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005739&_mathId=si17.gif&_user=111111111&_pii=S0166218X15005739&_rdoc=1&_issn=0166218X&md5=8941d82c12d175b92d07c31d6d815591" title="Click to view the MathML source">kan>an class="mathContainer hidden">an class="mathCode">ath altimg="si17.gif" overflow="scroll">kath>an>an>an>-approximation algorithm for the minimum (cardinality) an id="mmlsi22" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005739&_mathId=si22.gif&_user=111111111&_pii=S0166218X15005739&_rdoc=1&_issn=0166218X&md5=687122783f5c884f2b88c16d98745fed" title="Click to view the MathML source">CVCP_kan>an class="mathContainer hidden">an class="mathCode">ath altimg="si22.gif" overflow="scroll">CVCPkath>an>an>an> problem under the assumption that the graph has girth at least an id="mmlsi17" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005739&_mathId=si17.gif&_user=111111111&_pii=S0166218X15005739&_rdoc=1&_issn=0166218X&md5=8941d82c12d175b92d07c31d6d815591" title="Click to view the MathML source">kan>an class="mathContainer hidden">an class="mathCode">ath altimg="si17.gif" overflow="scroll">kath>an>an>an>. An example is given showing that performance ratio an id="mmlsi17" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005739&_mathId=si17.gif&_user=111111111&_pii=S0166218X15005739&_rdoc=1&_issn=0166218X&md5=8941d82c12d175b92d07c31d6d815591" title="Click to view the MathML source">kan>an class="mathContainer hidden">an class="mathCode">ath altimg="si17.gif" overflow="scroll">kath>an>an>an> is asymptotically tight for our algorithm.