A Polynomial Algorithm for Weighted Toughness of Interval Graphs - Ming Shi; Zongtian Wei (Journal of Mathematics)
The concept of toughness, introduced by Chva´tal, has been widely used as an important invulnerability parameter. This parameter is generalized to weighted graphs, and the concept of weighted toughness is proposed. A polynomial algorithm for computing the weighted toughness of interval graphs is given.