پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 158 |
| تعداد شماره‌ها | 6,230 |
| تعداد مقالات | 67,760 |
| تعداد مشاهده مقاله | 115,141,435 |
| تعداد دریافت فایل اصل مقاله | 89,903,670 |
Tenacity and some other Parameters of Interval Graphs can be computed in polynomial time | ||
| Journal of Algorithms and Computation | ||
| مقاله 6، دوره 50، issue 2، اسفند 2018، صفحه 81-87 اصل مقاله (249.89 K) | ||
| نوع مقاله: Research Paper | ||
| شناسه دیجیتال (DOI): 10.22059/jac.2018.69783 | ||
| نویسندگان | ||
| Dara Moazzami* 1؛ Niloofar Vahdat2 | ||
| 1University of Tehran, College of Engineering, Faculty of Engineering Science | ||
| 2University of Tehran, Department of Algorithms and Computation | ||
| چکیده | ||
| In general, computation of graph vulnerability parameters is NP-complete. In past, some algorithms were introduced to prove that computation of toughness, scattering number, integrity and weighted integrity parameters of interval graphs are polynomial. In this paper, two different vulnerability parameters of graphs, tenacity and rupture degree are defined. In general, computing the tenacity of a graph is NP-hard and the rupture degree of a graph is NP-complete, but in this paper, we will show that these parameters can be computed in polynomial time for interval graphs. | ||
| کلیدواژه‌ها | ||
| Vulnerability parameters؛ Tenacity؛ rupture degree؛ Interval graphs | ||
|
آمار تعداد مشاهده مقاله: 207 تعداد دریافت فایل اصل مقاله: 141 |
||