On the Independent Set Interdiction Problem
2015  //  DOI: 10.5614/ejgta.2015.3.2.2
Gholam Hassan Shirdel, Nasrin Kahkeshani

Metrik

  • Eye Icon 160 kali dilihat
  • Download Icon 50 downloads
Metrics Icon 160 kali dilihat  //  50 downloads
Abstrak

The purpose of the independent set interdiction problem in the weighted graph $G$ is to determine a set of vertices $R^*$ such that the weight of the maximum independent set in $G-R^*$ is minimized. We define an approximate solution for this problem. Then, an upper bound for the relative error of this problem is obtained. We show that the limit of the relative error of the independent set interdiction problem in some subclasses of the generalized Petersen graphs is zero as the number of vertices tends to infinity.

Full text
Show more arrow
 
More from this journal
On Open Neighborhood Locating-dominating in Graphs
Chromatically Unique 6-bridge Graph Theta(a,a,a,b,b,c)
On Imbalances In Multipartite Multidigraphs
🧐  Browse all from this journal

Metrik

  • Eye Icon 160 kali dilihat
  • Download Icon 50 downloads
Metrics Icon 160 kali dilihat  //  50 downloads