A polynomial algorithm for weighted scattering number in interval graphs

Fengwei Li, Xiaoyan Zhang, Hajo Broersma

Research output: Contribution to journalArticleAcademicpeer-review

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 languageEnglish
Pages (from-to)118-124
Number of pages7
JournalDiscrete applied mathematics
Volume264
Early online date16 Feb 2019
DOIs
Publication statusPublished - 15 Jul 2019

Keywords

  • Scattering number
  • Weighted scattering number
  • Toughness
  • Network vulnerability
  • Interval graph
  • Local cut

Fingerprint Dive into the research topics of 'A polynomial algorithm for weighted scattering number in interval graphs'. Together they form a unique fingerprint.

  • Cite this