Safe set problem on graphs

详细信息    查看全文

• 作者：Shinya Fujita^a ; ^{shinya.fujita.ph.d@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Gary MacGillivray^b ; ^{gmacgill@uvic.ca" class="auth_mail" title="E-mail the corresponding author} ; Tadashi Sakuma^c ; ^{sakuma@e.yamagata-u.ac.jp" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Facility location problem ; Safe set
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：31 December 2016
• 年：2016
• 卷：215
• 期：Complete
• 页码：106-111
• 全文大小：375 K

文摘

A non-empty subset class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16303511&_mathId=si1.gif&_user=111111111&_pii=S0166218X16303511&_rdoc=1&_issn=0166218X&md5=b961b0a71bdd152cbf0617d619df202c" title="Click to view the MathML source">Sclass="mathContainer hidden">class="mathCode">$S$ of the vertices of a connected graph class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16303511&_mathId=si2.gif&_user=111111111&_pii=S0166218X16303511&_rdoc=1&_issn=0166218X&md5=04cab4915ce67d3c137ce62e8ddc7c04" title="Click to view the MathML source">G=(V(G),E(G))class="mathContainer hidden">class="mathCode">$G=(V\left(G\right),E\left(G\right))$ is a safe set   if, for every connected component class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16303511&_mathId=si3.gif&_user=111111111&_pii=S0166218X16303511&_rdoc=1&_issn=0166218X&md5=e3e94f9509c3235fc7aec5ff4d134fba" title="Click to view the MathML source">Cclass="mathContainer hidden">class="mathCode">$C$ of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16303511&_mathId=si4.gif&_user=111111111&_pii=S0166218X16303511&_rdoc=1&_issn=0166218X&md5=2ff15e2437a44f01d28500684cedaa4b" title="Click to view the MathML source">G[S]class="mathContainer hidden">class="mathCode">$G\left[S\right]$ and every connected component class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16303511&_mathId=si5.gif&_user=111111111&_pii=S0166218X16303511&_rdoc=1&_issn=0166218X&md5=8debfa3843ac76830e556cd33c685cfc" title="Click to view the MathML source">Dclass="mathContainer hidden">class="mathCode">$D$ of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16303511&_mathId=si6.gif&_user=111111111&_pii=S0166218X16303511&_rdoc=1&_issn=0166218X&md5=19c768e9ef8dabb8ccb70a707063119c" title="Click to view the MathML source">G−Sclass="mathContainer hidden">class="mathCode">$G-S$, we have class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16303511&_mathId=si7.gif&_user=111111111&_pii=S0166218X16303511&_rdoc=1&_issn=0166218X&md5=b051768036cfbf9535a0c41612fec9e4" title="Click to view the MathML source">|C|≥|D|class="mathContainer hidden">class="mathCode">$\left|C\right|\ge \left|D\right|$ whenever there exists an edge of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16303511&_mathId=si8.gif&_user=111111111&_pii=S0166218X16303511&_rdoc=1&_issn=0166218X&md5=d6a5bb4e90638608f34d424b06f37220" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$ between class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16303511&_mathId=si3.gif&_user=111111111&_pii=S0166218X16303511&_rdoc=1&_issn=0166218X&md5=e3e94f9509c3235fc7aec5ff4d134fba" title="Click to view the MathML source">Cclass="mathContainer hidden">class="mathCode">$C$ and class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16303511&_mathId=si5.gif&_user=111111111&_pii=S0166218X16303511&_rdoc=1&_issn=0166218X&md5=8debfa3843ac76830e556cd33c685cfc" title="Click to view the MathML source">Dclass="mathContainer hidden">class="mathCode">$D$. If class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16303511&_mathId=si4.gif&_user=111111111&_pii=S0166218X16303511&_rdoc=1&_issn=0166218X&md5=2ff15e2437a44f01d28500684cedaa4b" title="Click to view the MathML source">G[S]class="mathContainer hidden">class="mathCode">$G\left[S\right]$ is connected, then class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16303511&_mathId=si1.gif&_user=111111111&_pii=S0166218X16303511&_rdoc=1&_issn=0166218X&md5=b961b0a71bdd152cbf0617d619df202c" title="Click to view the MathML source">Sclass="mathContainer hidden">class="mathCode">$S$ is called a connected safe set. We discuss the minimum sizes of safe sets and connected safe sets in connected graphs.