Abstract
The scattering number of a graph was introduced by Jung (1978) in relation to hamiltonian properties and network vulnerability, and it can also be regarded as the additive analogue of the toughness introduced by Chvátal. In this paper, we consider the problem of computing a generalized variant, namely the weighted scattering number. In general, computing the scattering number of a graph is NP-hard. Here we investigate the computational complexity of the weighted scattering number and give a polynomial time algorithm for computing this parameter when the input graph is an interval graph. Our results generalize the algorithm given by Broersma et al. (2015) which can only deal with the unweighted case, i.e., the special case when all the vertex weights are equal to 1.
Original language | English |
---|---|
Pages (from-to) | 118-124 |
Number of pages | 7 |
Journal | Discrete applied mathematics |
Volume | 264 |
Early online date | 16 Feb 2019 |
DOIs | |
Publication status | Published - 15 Jul 2019 |
Keywords
- Scattering number
- Weighted scattering number
- Toughness
- Network vulnerability
- Interval graph
- Local cut