سامانه پشتیبانی خدمات اطلاعات

  اخبار و اعلانات

 آمار

تعداد نشریات161
تعداد شماره‌ها6,573
تعداد مقالات71,037
تعداد مشاهده مقاله125,520,947
تعداد دریافت فایل اصل مقاله98,780,501
Hashemipour, Maliheh, Hooshmandasl, Mohammadreza, Shakiba, Ali. (1398). On the outer-connected reinforcement and bondage problems in bipartite graphs: the algorithmic complexity. , 51(2), 63-74. doi: 10.22059/jac.2019.75163
Maliheh Hashemipour; Mohammadreza Hooshmandasl; Ali Shakiba. "On the outer-connected reinforcement and bondage problems in bipartite graphs: the algorithmic complexity". , 51, 2, 1398, 63-74. doi: 10.22059/jac.2019.75163
Hashemipour, Maliheh, Hooshmandasl, Mohammadreza, Shakiba, Ali. (1398). 'On the outer-connected reinforcement and bondage problems in bipartite graphs: the algorithmic complexity', , 51(2), pp. 63-74. doi: 10.22059/jac.2019.75163
Hashemipour, Maliheh, Hooshmandasl, Mohammadreza, Shakiba, Ali. On the outer-connected reinforcement and bondage problems in bipartite graphs: the algorithmic complexity. , 1398; 51(2): 63-74. doi: 10.22059/jac.2019.75163

On the outer-connected reinforcement and bondage problems in bipartite graphs: the algorithmic complexity

Journal of Algorithms and Computation
مقاله 6، دوره 51، شماره 2، اسفند 2019، صفحه 63-74    اصل مقاله (269.29 K)
نوع مقاله: Research Paper
شناسه دیجیتال (DOI): 10.22059/jac.2019.75163
نویسندگان
Maliheh Hashemipour1؛ Mohammadreza Hooshmandasl1؛ Ali Shakiba2
1Department of Computer Science, Yazd University, Yazd, Iran.
2Department of Computer Science, Vali-e-Asr University of Rafsanjan, Rafsanjan, Iran.
چکیده
An outer connected dominating(OCD) set of a graph $G=(V,E)$ is a set $\tilde{D} \subseteq V$ such that every vertex not in $S$ is adjacent to a vertex in $S$, and the induced subgraph of $G$ by $V \setminus \tilde{D}$, i.e. $G [V \setminus \tilde{D}]$, is connected. The OCD number of $G$ is the smallest cardinality of an OCD set of $G$. The outer-connected bondage number of a nonempty graph G is the smallest number of edges whose removal from G results in a graph with a larger OCD number. Also, the outer-connected reinforcement number of G is the smallest number of edges whose addition to G results in a graph with a smaller OCD number. In 2018, Hashemi et al. demonstrated that the decision problems for the Outer-Connected Bondage and the Outer-Connected Reinforcement numbers are all NP-hard in general graphs. In this paper, we improve these results and show their hardness for bipartite graphs. Also, we obtain bounds for the outer-connected bondage number.
کلیدواژه‌ها
Bipartite graphs؛ Outer-connected domination؛ Bondage؛ Reinforcement؛ Complexity
آمار
تعداد مشاهده مقاله: 287
تعداد دریافت فایل اصل مقاله: 201





سامانه مدیریت نشریات علمی. قدرت گرفته از سیناوب