The maximum infection time in the geodesic and monophonic convexities

详细信息    查看全文

• 作者：Fabrí ; cio Benevides^a ; ¹ ; ^{fabricio@mat.ufc.br" class="auth_mail" title="E-mail the corresponding author} ; Victor Campos^a ; ¹ ; ^{campos@lia.ufc.br" class="auth_mail" title="E-mail the corresponding author} ; Mitre C. Dourado^b ; ¹ ; ^{mitre@dcc.ufrj.br" class="auth_mail" title="E-mail the corresponding author} ; Rudini M. Sampaio^a ; ¹ ; ^{rudini@lia.ufc.br" class="auth_mail" title="E-mail the corresponding author} ; Ana Silva^a ; ¹ ; ^{anasilva@mat.ufc.br" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Geodesic convexity ; Maximum infection time ; Monophonic hull number ; Monophonic convexity
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：4 January 2016
• 年：2016
• 卷：609
• 期：part_P2
• 页码：287-295
• 全文大小：373 K

文摘

Recent papers investigated the maximum infection time class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515008816&_mathId=si1.gif&_user=111111111&_pii=S0304397515008816&_rdoc=1&_issn=03043975&md5=1a589ec99863aca28d6581551b86ddc2" title="Click to view the MathML source">t_P3(G)class="mathContainer hidden">class="mathCode">$t_{P3}(G)$ of the class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515008816&_mathId=si2.gif&_user=111111111&_pii=S0304397515008816&_rdoc=1&_issn=03043975&md5=1ee094cb3efc5ff3cdd2b884c1e3f6bc" title="Click to view the MathML source">P₃class="mathContainer hidden">class="mathCode">$P_3$-convexity (also called maximum time of 2-neighbor bootstrap percolation) and the maximum infection time class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515008816&_mathId=si3.gif&_user=111111111&_pii=S0304397515008816&_rdoc=1&_issn=03043975&md5=99da4fa93988f6e23fa20b876b2ffc3c" title="Click to view the MathML source">t_mo(G)class="mathContainer hidden">class="mathCode">$t_{mo}(G)$ of the monophonic convexity. In 2014, it was proved that, for bipartite graphs, deciding whether class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515008816&_mathId=si4.gif&_user=111111111&_pii=S0304397515008816&_rdoc=1&_issn=03043975&md5=c9403b71d9fa66ed8bea6dd8cbaa10a5" title="Click to view the MathML source">t_P3(G)≥kclass="mathContainer hidden">class="mathCode">$t_{P3}(G)\ge k$ is polynomial time solvable for class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515008816&_mathId=si33.gif&_user=111111111&_pii=S0304397515008816&_rdoc=1&_issn=03043975&md5=fb2d4368ecab94addc8b8970a1b445b9" title="Click to view the MathML source">k≤4class="mathContainer hidden">class="mathCode">$k\le 4$, but is NP-complete for class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515008816&_mathId=si34.gif&_user=111111111&_pii=S0304397515008816&_rdoc=1&_issn=03043975&md5=025cb14019673e70434c2a5f16189216" title="Click to view the MathML source">k≥5class="mathContainer hidden">class="mathCode">$k\ge 5$[23]. In 2015, it was proved that deciding whether class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515008816&_mathId=si7.gif&_user=111111111&_pii=S0304397515008816&_rdoc=1&_issn=03043975&md5=cfddb59840df171dac80f7c66d20dada" title="Click to view the MathML source">t_mo(G)≥2class="mathContainer hidden">class="mathCode">$t_{mo}(G)\ge 2$ is NP-complete even for bipartite graphs [12]. In this paper, we investigate the maximum infection time class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515008816&_mathId=si8.gif&_user=111111111&_pii=S0304397515008816&_rdoc=1&_issn=03043975&md5=a7719988de712dfe6d2720450a1fcffe" title="Click to view the MathML source">t_gd(G)class="mathContainer hidden">class="mathCode">$t_{gd}(G)$ of the geodesic convexity. We prove that deciding whether class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515008816&_mathId=si9.gif&_user=111111111&_pii=S0304397515008816&_rdoc=1&_issn=03043975&md5=c0aabf8b86a8efd327e8682d0926cf57" title="Click to view the MathML source">t_gd(G)≥kclass="mathContainer hidden">class="mathCode">$t_{gd}(G)\ge k$ is polynomial time solvable for class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515008816&_mathId=si10.gif&_user=111111111&_pii=S0304397515008816&_rdoc=1&_issn=03043975&md5=1f3c0acd5d863f68c327d5e43b028652" title="Click to view the MathML source">k=1class="mathContainer hidden">class="mathCode">$k=1$, but is NP-complete for class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515008816&_mathId=si11.gif&_user=111111111&_pii=S0304397515008816&_rdoc=1&_issn=03043975&md5=3c98a274881c8533e7c21ed0b84d7a2a" title="Click to view the MathML source">k≥2class="mathContainer hidden">class="mathCode">$k\ge 2$ even for bipartite graphs. We also present an class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515008816&_mathId=si12.gif&_user=111111111&_pii=S0304397515008816&_rdoc=1&_issn=03043975&md5=4743c282161fc7d1d3595b800da07a1b" title="Click to view the MathML source">O(n³m)class="mathContainer hidden">class="mathCode">$O(n^{3}m)$-time algorithm to determine class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515008816&_mathId=si8.gif&_user=111111111&_pii=S0304397515008816&_rdoc=1&_issn=03043975&md5=a7719988de712dfe6d2720450a1fcffe" title="Click to view the MathML source">t_gd(G)class="mathContainer hidden">class="mathCode">$t_{gd}(G)$ and class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515008816&_mathId=si3.gif&_user=111111111&_pii=S0304397515008816&_rdoc=1&_issn=03043975&md5=99da4fa93988f6e23fa20b876b2ffc3c" title="Click to view the MathML source">t_mo(G)class="mathContainer hidden">class="mathCode">$t_{mo}(G)$ in distance-hereditary graphs. For this, we characterize all minimal hull sets of a general graph in the monophonic convexity. Moreover, we improve the complexity of the fastest known algorithm for finding a minimum hull set of a general graph in the monophonic convexity.