Computing the Weighted Isolated Scattering Number of Interval Graphs in Polynomial Time
Joint Authors
Zhang, Xiaoyan
Li, Fengwei
Ye, Qingfang
Sun, Yuefang
Source
Issue
Vol. 2019, Issue 2019 (31 Dec. 2019), pp.1-8, 8 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2019-03-10
Country of Publication
Egypt
No. of Pages
8
Main Subjects
Abstract 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.
American Psychological Association (APA)
Li, Fengwei& Zhang, Xiaoyan& Ye, Qingfang& Sun, Yuefang. 2019. Computing the Weighted Isolated Scattering Number of Interval Graphs in Polynomial Time. Complexity،Vol. 2019, no. 2019, pp.1-8.
https://search.emarefa.net/detail/BIM-1131782
Modern Language Association (MLA)
Li, Fengwei…[et al.]. Computing the Weighted Isolated Scattering Number of Interval Graphs in Polynomial Time. Complexity No. 2019 (2019), pp.1-8.
https://search.emarefa.net/detail/BIM-1131782
American Medical Association (AMA)
Li, Fengwei& Zhang, Xiaoyan& Ye, Qingfang& Sun, Yuefang. Computing the Weighted Isolated Scattering Number of Interval Graphs in Polynomial Time. Complexity. 2019. Vol. 2019, no. 2019, pp.1-8.
https://search.emarefa.net/detail/BIM-1131782
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1131782