Computing the Weighted Isolated Scattering Number of Interval Graphs in Polynomial Time

الملخص EN

The scattering number and isolated scattering number of a graph have been introduced in relation to Hamiltonian properties and network vulnerability, and the isolated scattering number plays an important role in characterizing graphs with a fractional 1-factor.

Here we investigate the computational complexity of one variant, namely, the weighted isolated scattering number.

We give a polynomial time algorithm to compute this parameter of interval graphs, an important subclass of perfect graphs.