Computing the Weighted Isolated Scattering Number of Interval Graphs in Polynomial Time. (10th March 2019)

• Record Type: Journal Article
• Authors: Li, Fengwei; Zhang, Xiaoyan; Ye, Qingfang; Sun, Yuefang
• Other Names: Martínez Eulalia Academic Editor.
• Is Part Of: Complexity. Volume 2019(2019)
• Publication Date: 2019-03-10
• Subjects: Chaotic behavior in systems -- Periodicals; Complexity (Philosophy) -- Periodicals; 003
• DOI: 10.1155/2019/4318261
• Languages: English
• ISSNs: 1076-2787

Abstract

Abstract : 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.