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

Authors: Fengwei Li; Xiaoyan Zhang; Qingfang Ye; Yuefang Sun
Journal: Complexity
 (2019)

---

## 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.


---

## Body

## 1. Introduction

Throughout this paper, we use Bondy and Murty [1] for terminology and notations not defined here, and we consider finite simple undirected graphs only. The vertex set of a graph G is denoted by V(G) (or just V if this does not cause confusion) and the edge set by E(G) (or just E). For a proper subset X⊂V(G), let c(G-X) and i(G-X) denote the number ofcomponents and the number ofisolated vertices (vertices with degree 0) in G-X, respectively. If X⊆V(G) is a nonempty subset, we use G[X] to denote the subgraph of G induced by X. A subset X⊂V is avertex cut of a graph G=(V,E) if c(G-X)≥2. We use C(G) to denote the set of all vertex cuts of G.The scattering number of a graph was introduced by Jung [2] as a parameter related to Hamiltonian properties of the graph, but the scattering number has also been used as a measure for the vulnerability of graphs to disruption caused by the removal of vertices. Thescattering number of a noncomplete graph G is defined as (1)sG=max⁡cG-X-X:X⊂VG,cG-X≥2.Note thats(G)≤0 if G has a Hamilton cycle, i.e., a cycle containing all the vertices of G. Similarly, it is easy to see that s(G)≤k if the vertex set of G can be covered by k vertex-disjoint paths.Motivated by Jung’s scattering number, replacingc(G-X) with i(G-X) in the above definition of s(G), Wang et al. [3] introduced the isolated scattering number, isc(G), as a new parameter to measure the vulnerability of networks.Definition 1.
Theisolated scattering number of a noncomplete graph G is defined as (2)iscG=max⁡iG-X-X:X∈CG,where the maximum is taken over all vertex cuts of G.The isolated scattering number is strongly related to the existence of fractional1-factor of graphs, as we will demonstrate in the following paragraph. We first recall the definition of a fractional k-factor.Letf:E(G)→[0,1] be a real-valued function from the edge set E(G) of a graph G to the real number interval [0,1]. For any e∈E(G), f(e) is referred to as theweight of the edge e. Define Ef=e∈EG:fe>0 and let G[Ef] be the spanning subgraph of G with edge set Ef. If the sum of the weights of all the edges incident with a vertex v is k for every vertex v∈V(G), then G[Ef] is called afractionalk-factor of G. A fractional 1-factor is also referred to as afractional perfect matching [4].The following theorem provides a characterization for the existence of fractional 1-factors in terms ofisc(G).Theorem 2 (see [4]).
A graphG has a fractional 1-factor if and only if i(G-X)≤X for any X⊆V(G).This shows, in particular, that a noncomplete connected graphG has a fractional 1-factor if and only if isc(G)≤0.Fractional factors have wide-ranging applications in areas such as network design and scheduling. For instance, if we allow several large data packets to be sent to various destinations through several channels in a communication network, the efficiency of the network can be improved if large data packets are partitioned into smaller packets. The feasible assignment of data packets to channels can be modelled as a fractional flow problem, and it becomes a fractional matching problem when the destinations and sources of the network are disjoint (i.e., the underlying graph is bipartite).The isolated scattering number is also of particular interest because it is considered to be a reasonable alternative measure for the vulnerability of graphs. It is not difficult to construct examples of graphs (of the same order) with the same scattering number but different isolated scattering numbers.In many applications where graph models are used to model networks, different vertices of the graph have different characteristics such as computing power, speed, costs, power consumption, capacity of jobs being executed, protection mechanisms, and life cycle in the corresponding network. In such cases, assigning equal importance to the vertices is neither desirable nor realistic. To dodge this situation, vertex weights are usually introduced in graph models to address the difference in importance. In this paper, we introduce the following weighted variant of the isolated scattering number.Definition 3.
Theweighted isolated scattering number of a noncomplete graph G=(V,E) is defined as (3)iscwG=max⁡iG-X-wX:X∈CG,where w:V→Q+ is a positive vertex weight function and Q+ denotes the set of positive rational numbers which are larger or equal to 1. Here w(X)=∑v∈Xw(v), and the maximum has taken over all vertex cuts of G. For convenience, we define iscw(Kn)=-∞.Definition 4.
For a noncomplete graphG and weight function w:V→Q+, a vertex cut X⊂V(G) is called anattaining cut of G if iscw(G)=i(G-X)-w(X).Clearly, this weighted variant reduces to the original isolated scattering number when all vertex weights are equal to 1. While computing the scattering number is NP-hard in general [5], the scattering number can be computed in linear time for interval graphs [6].In 2017, Shi et al. [7] presented some new bounds for the scattering number of regular graphs in terms of the spectrum. We are only aware of a few algorithmic and complexity results dealing with the isolated scattering number. In [3], Wang et al. gave formulas for the isolated scattering number of join graphs and some bounds of the isolated scattering number, and they also gave a polynomial time algorithm for computing the isolated scattering number of trees. In [8], the authors proved that for split graphs the isolated scattering number can be computed in polynomial times and they also determined the isolated scattering number of the Cartesian product and the Kronecker product of special graphs and that of special permutation graphs.In contrast, interval graphs are a large class of widely studied graphs, both theoretically and in applications. We recall the definition of an interval graph for convenience.Definition 5 (see [9]).
A graphG is called aninterval graph if its vertices can be put into one to one correspondence with a set of intervals l of a linearly ordered set (like the real line) such that two vertices are joined by an edge if and only if their corresponding intervals have a nonempty intersection. In this case, we call l aninterval representation for G.Interval graphs are a well-known family of perfect graphs [9] with many nice structural properties and applications [10–13]. An extensive discussion of interval graphs is available in [14]. In addition to these, relations between the interval graphs of a Boolean function have been studied intensely. Toman et al. [15] obtained asymptotic estimation of vertex degree in the interval graph of a random Boolean function. In [16], Daubner et al. estimated the size of a neighbourhood of constant order in the interval graph of a random Boolean function. For more about interval graph of a Boolean function, one can see [17–19]. Kratsch et al. [20] gave the first polynomial time algorithms for computing the toughness and the scattering number for interval graphs. Broersma et al. [6] gave O(n+m) time algorithm for computing the scattering number of an interval graph with n vertices and m edges. To the best of our knowledge, there is no known complexity result for computing the weighted isolated scattering number of an interval graph.The rest of the paper is organized as follows. In the next section, we start with some additional definitions and notation and present some preliminary results that are used to characterize properties of an attaining cut and give a formula for computing the weighted isolated scattering number of a noncomplete connected interval graph from its minimal local cuts. Then a polynomial algorithm for computing the weighted isolated scattering number of an interval graph was presented, which is based on dynamic programming on segments. This is followed by a correctness proof and an analysis of the time complexity. Finally, we give some concluding remarks in Section3.


## 2. Weighted Isolated Scattering Number of Interval Graphs

In this section, we characterize the properties of an attaining cutX of a graph G and give a polynomial time algorithm for computing the weighted isolated scattering number of interval graphs.The number of possible vertex cuts of a general graph can be exponentially large. Therefore, no enumerative scheme could possibly lead to a polynomial time algorithm. However, for an interval graph, one needs not consider all vertex cuts exhaustively in order to compute the weighted isolated scattering number. The following definitions and lemmas that are mostly adopted from literature and adapted to our situation help us to reduce the size of the search space. In fact, in most of what follows we adapt the setup due to Ray et al. [21]. They introduced the following useful concept.Definition 6 (see [21]).
For a graphG, a vertex cut X⊂V(G) is called astrong cut of G if, for every proper subset Y⊂X, the number of components of G-X is strictly larger than the number of components of G-Y.The usefulness of the above concept is illustrated by the following simple result.Lemma 7.
For any graphG, there is an attaining cut X⊂V(G) such that X is a strong cut of G.Proof.
LetX be an attaining cut of the graph G that is not a strong cut. By the definition of strong cut, we know that there exists a vertex u∈X such that the number of components of G-X is the same as the number of components of G-(X∖u); i.e., c(G-X)=c(G-(X∖u)). Let X1=X∖u. Now, i(G-X)=i(G-X1) or i(G-X)=i(G-X1)+1. Moreover, w(X1)+w(u)=w(X). We distinguish two cases.
Case 1 (i(G-X)=i(G-X1)). Then (4)iG-X1-wX1=iG-X-wX+wu>iG-X-wX,a contradiction to the definition of the weighted isolated scattering number. Hence, X is a strong cut of G.
Case 2 (i(G-X)=i(G-X1)+1). Then (5)iG-X1-wX1=iG-X-1-wX+wu.
Subcase 2.1 (w(u)=1). (6)iG-X1-wX1=iG-X-1-wX+wu=iG-X-wX.If X1 is a strong cut, then the lemma is proved. If not, the same construction may be repeated on X1 until a strong cut is obtained. Obtaining a strong cut is guaranteed because any vertex cut consisting of one vertex is a strong cut.
Subcase 2.2 (w(u)>1), (7)iG-X1-wX1=iG-X-1-wX+wu>iG-X-wX,a contradiction to the definition of the weighted isolated scattering number. Hence, X is a strong cut of G.
This completes the proof.We use the following well-known lemma.Lemma 8 (see [9]).
Any induced subgraph of an interval graph is an interval graph.For the rest of the paper we shall adopt the following notation. Given an interval graphG=(V,E) where V=v1,v2,…,vn, suppose that G is isomorphic to the intersection graph of the intervals [ai,bi] for i=1,2,…,n. The interval [ai,bi] will be called theinterval attached to the vertex vi for i=1,2,…,n, and ai will be called theleft end point and bi theright end point. Furthermore, we assume that not two of these intervals have the same end points; i.e., ai≠aj, bi≠bj for i≠j, and ai≠bj for all i,j. There is no limitation. For a detailed discussion about interval graphs, the interested reader is referred to [22]. Given an interval graph G=(V,E), consider a point x on the part of the real line covered by the intervals attached to the vertices of G. Let C(x)=vi:x∈ai,bi. Obviously, if mini⁡bi<x<maxi⁡ai, then C(x) defines a vertex cut of G. The following definition and lemma, also adopted from [21], establish a relationship between strong cuts and the sets C(x) for an interval graph.Definition 9.
LetG be an interval graph with the above representation. Consider a point x such that mini⁡bi<x<maxi⁡ai. If the end point immediately to the left of x is a right end point and the end point immediately to the right of x is a left end point, then C(x) is called aminimal local (vertex) cut.For brevity, minimal local (vertex) cuts will be called local cuts in the rest of the paper. Figures1 and 2 give examples of local cuts for interval graph and weighted interval graph, respectively.Figure 1
An example of an interval graph and its local cuts.Figure 2
A weighted interval graphG1 with weights w(I1)=1, w(I2)=3, w(I3)=2, w(I4)=2, w(I5)=1.2, w(I6)=2, w(I7)=2, w(I8)=2 and its associated adjacency matrix, local cuts.Lemma 10 (see [21]).
Any strong cut of an interval graph can be expressed as a union of local cuts.By combining Lemmas7 and 10, we know that any attaining set can be expressed as a union of local cuts. This can be shown as follows. Consider graphs G1 and G2 in Figures 2 and 3, It is not difficult to check that G1 and G2 have the same total weights of vertices; i.e., w(V(G1))=w(V(G2))=15.2, but iscw(G1)=-1≠0=iscw(G2). The attaining sets of G1 and G2 are {I7} and {I2}, respectively. It is obvious that these two attaining sets are both the union of local cuts.Figure 3
A weighted interval graphG2 with weights w(I1)=2, w(I2)=1, w(I3)=1.5, w(I4)=2, w(I5)=2.5, w(I6)=1, w(I7)=3, w(I8)=2.2.In the following theorem, we give a formula for computing the weighted isolated scattering number of a noncomplete interval graph.LetG be an interval graph. If G is complete, then iscw(G)=-∞. Otherwise, we have the following result.Theorem 11.
LetG be a noncomplete interval graph. Then (8)iscwG=maxX∗⁡∑i=l+1tmax⁡iscwGQi,0-wX∗+l,where the maximum has taken over all local cuts X∗ of the graph G, Q1,Q2,…,Ql are the components of G-X∗ which consist of isolated vertices, and Ql+1,Ql+2,…,Qt are the other components of G-X∗.Proof.
In order to obtain an upper bound foriscw(G), let X be an attaining cut with the minimum number of vertices among all attaining cuts of G. Let X∗ be a local cut of G that is a subset of X, and suppose Q1,Q2,…,Ql are the components of G-X∗ consisting of isolated vertices, and Ql+1,Ql+2,…,Qt are the other components of G-X∗. It is easy to see that Q1,Q2,…,Ql are also components of G-X, so, we consider the sets Xi=X∩Qi, i∈l+1,l+2,…,t. The proof proceeds with the following two cases.
Case 1 (Xi=∅). Then, Qi is also a component of G-X, and we have i(G[Qi]-Xi)-w(Xi)=0.
Case 2 (Xi≠∅; i.e., Xi≥1). Suppose that Xi is not a vertex cut of G[Qi]. Then we have i(G-(X∖Xi))≥i(G-X)-1.
Subcase 2.1. If Xi=1, then (9)iG-X∖Xi-wX∖Xi≥iG-X-1-wX+wXi≥iG-X-wX=iscwG;i.e., X∖Xi is also an attaining cut of G, a contradiction to the minimality of X.
Subcase 2.2. If Xi>1, then (10)iG-X∖Xi-wX∖Xi≥iG-X-1-wX+wXi>iG-X-wX=iscwG,a contradiction to the definition of the weighted isolated scattering number. Hence, Xi≠∅ implies that Xi is a vertex cut of G[Qi]. Thus, (11)iscwGQi≥iGQi-Xi-wXi.Furthermore, we have (12)iscwG=iG-X-wX=∑i=l+1tiGQi-Xi-wXi-wX∗+l≤∑i=l+1tmax⁡iscwGQi,0-wX∗+l.
In order to obtain an lower bound foriscw(G), let X∗ be a local cut of G with c(G-X∗)≥2. Furthermore, let Q1,Q2,…,Ql be the components of G-X∗ consisting of isolated vertices, and let Ql+1,Ql+2,…,Qt be the other components of G-X∗. Then we construct a vertex cut of G such that X=X∗∪(⋃i=l+1tXi) with Xi⊂Qi for every i∈{l+1,l+2,…,t}. For i∈{l+1,l+2,…,t}, we set Xi=∅ if iscw(G[Qi])≤0. Otherwise, if iscw(G[Qi])>0, we choose a vertex cut Xi of G[Qi] such that iscw(G[Qi])=i(G[Qi]-Xi)-w(Xi). Then X⊃X∗ is a vertex cut of G and we have (13)iscwG≥iG-X-wX=∑i=l+1tiGQi-Xi-wXi-wX∗+l.
Without loss of generality, letQl+1,Ql+2,…,Ql+r, 0≤r≤t-l, be the components of G with iscw(G[Qi])≤0. Consequently, (14)iscwG≥∑i=l+1tiGQi-Xi-wXi-wX∗+l=∑i=l+1l+r0+∑i=l+r+1tiscwGQi-wX∗+l=∑i=l+1tmax⁡iscwGQi,0-wX∗+l.Combining the upper and lower bounds for iscw(G), we obtain the desired expression. This completes the proof.From Theorem11 we know that the weighted isolated scattering number of a noncomplete interval graph can be computed via its local cuts. Back in 2006, Ray et al. presented Algorithm 1 for computing all local cuts of an interval graph [21]. It has been proved that a naive implementation of Algorithm 1 executes in O(n2) time.Algorithm 1:Algorithm minimal local cuts.
Input: An interval graph G and its interval representation. Let V(G)={v1,v2,…,vn} with vi represented by [ai,bi] for i=1,2,…,n. Furthermore, let all ai and bi be distinct. Output: Minimal local cuts C(α1),…,C(αk) Data structure: end-points of type record containing two fields, value: real and att∈left,right 1 begin 2 Construct records of type end-points x1,x2,…,xn, as follows; 3  for  i=1,…,n  do 4  x 2 i - 1.value ←ai;  x2i-1.att ← left; 5  x 2 i.value ←bi;  x2i.att ← right; 6  end 7 Sort x1,x2,⋯,xn in non-decreasing order using value as key. Let the sorted form be y1,y2,…,y2n; 8  k ← 0; i←miny2j.att=right⁡j; v←yi.value; 9  for  i←2 to 2n  do 10  if  yi.att=left andyi-1.att= right andyi.value>v  then 11  k ← k + 1; 12  α k ← y i . v a l u e + y i - 1 . v a l u e 2; 13  C α k ← v p : y i . v a l u e ∈ a p , b p 14  end 15  end 16 endNow the problem of finding the weighted isolated scattering number of an interval graphG reduces to finding a attaining cut X of G such that X can be expressed as a union of local cuts, as generated by Algorithm 1.It is easy to see that Algorithm1 generates a linear order among the vertex cuts that it computes. This order is important and will be used in our algorithms later. Let the minimal local cuts generated by Algorithm 1 be C(α1),…,C(αk) (in the order they are generated). For convenience, we let α0=-∞, αk+1=+∞, and we define C(α0)=C(αk+1)=∅. Note that αis are sorted in nondecreasing order. Define comp(i,j)={vp:ap>αi,bp<αj}. Note that, for any vertex cut X consisting of the union of some of C(α1),…,C(αk), every component of G-X can be expressed in the form comp(i,j) for some i,j. A set comp(i,j), 1≤i≤j≤k, is said to be asegment of G if comp(i,j)≠∅ and G[comp(i,j)] is connected. Furthermore, V=comp(0,k+1) is a segment of G. For convenience, we let A={C(α1),C(α2),…,C(αk)}.Using the characterization of interval graph, we can easily identify the local cuts of a noncomplete segmentG[comp(i,j)].Lemma 12.
LetX be a minimal local cut of a noncomplete segment comp(i,j), 0≤i<j≤k+1. Then there exists a minimal local cut C(αp) of G, i<p<j, such that X=C(αp)∩comp(i,j). Moreover, every component of G[comp(i,j)∖X] is a segment of G.Proof.
By Lemma8, we know that G[comp(i,j)] is an interval graph. Let X be a minimal local cut of G[comp(i,j)]. Then by the definition of a minimal local cut, there exists a set C(x)={vi:x∈[ai,bi]}, where the point x is on the part of the real line covered by the intervals attached to the vertices of G[comp(i,j)] such that mini⁡bi<x<maxi⁡ai, and the end point immediately to the left of x is a right end point, and the end point immediately to the right of x is a left end point. Then C(x) must also be a minimal local cut of G. Hence, there exists a C(αp) of G, i<p<j, such that C(x)=C(αp). Thus, we get X=C(αp)∩comp(i,j).
The graphG[comp(i,j)∖X] is either the disjoint union of G[comp(i,p)] and G[comp(p,j)] or equal to one of them (in case that comp(i,p)=∅ or comp(p,j)=∅). Hence, the set of components of G[comp(i,j)∖X] is equal to the union of the set of components of G[comp(i,p)] and of the set of components of G[comp(p,j)], or it is equal to one of these sets. Hence, all components of G[comp(i,j)∖X] are segments. This completes the proof.From the above, we know that there are essentially two different types of segmentscomp(i,j) in an interval graph. A segment comp(i,j) is calledcomplete if it induces a complete graph, and it is callednoncomplete otherwise. It is obvious that segments comp(i,i+1)(1≤i≤k) are complete. Furthermore, a segment comp(i,j), i<j, may also be complete. And for every complete segment comp(i,j), i<j, we have(15)iscwGcompi,j=-∞.For every noncomplete componentcomp(i,j), 0≤i<j≤k+1, we have(16)iscwGcompi,j=max⁡∑i=l+1tmax⁡iscwGQi,0-wCαp∩compi,j+l,where the maximum has taken over all local cuts C(αp)∩comp(i,j), p∈{i+1,…,j-1}, of G[comp(i,j)], Q1,Q2,…,Ql are the components of G[comp(i,j)∖C(αp)] consisting of isolated vertices, and Ql+1,Ql+2,…,Qt are the other components of G[comp(i,j)∖C(αp)].Now, we present our algorithm for computing the weighted isolated scattering number of interval graphs on the base of Theorem11 and Algorithm 1. See Algorithm 2.Algorithm 2:Algorithm weighted isolated scattering number.
Input: An interval graph G, as in Algorithm 1; Minimal local cuts C(α1),C(α2),…,C(αk), as generated by Algorithm 1. Output: Weighted Isolated scattering number iscw(G). 1 begin 2  α 0 ← - ∞; 3  α k + 1 ← + ∞; 4  C ( α 0 ) ← ∅; 5  C ( α k + 1 ) ← ∅; 6  for  i←0tokand forj←i+1tok+1  do 7 compute the vertex set comp(i,j); 8  if  comp(i,j)=∅  then 9 mark (i,j) “empty”; 10  end 11  if  comp(i,j)≠∅andG[comp(i,j)]is a complete induced subgraph  then 12 mark (i,j) “complete”. 13  end 14 For all nonmarked tuples (i,j), 0≤i<j≤k+1, check whether G[comp(i,j)] is connected; 15  if  G[comp(i,j)]  is connected  then 16 mark (i,j) “noncomplete” and for every p∈{i+1,…,j-1}, compute the components Q t = c o m p ( i t , j t ) of G[comp(i,j)∖C(αp)], 1≤it<jt≤k. Check whether C(αp)∩comp(i,j) is a minimal local cut of comp(i,j), and if so mark (p,i,j) “minimal”, store ( i 1 , j 1 ) , ( i 2 , j 2 ) , … , ( i k , j k ) in a linked list with a pointer from (p,i,j) to the head of this list, and compute Cαp∩compi,j. 17  end 18  if  G[comp(i,j)]is disconnected  then 19 compute the components Qt=comp(it,jt), 1 ≤ i t < j t ≤ k, of G[comp(i,j)] and store ( i 1 , j 1 ) , ( i 2 , j 2 ) , … , ( i t , j t ) in a linked list with a pointer from (i,j) to the head of this list. 20  end 21 For every pair (i,j) marked “complete”; 22  if  G[comp(i,j)]is of order 1  then 23 compute the number of such pair (i,j). 24  end 25  else if  the order ofG[comp(i,j)]is greater than 1  then 26 compute iscw(G[comp(i,j)]) according to equation (15). 27  for  d←1tokand fori←0tok-d+1  do 28 if (i,i+d) is marked “noncomplete” compute i s c w ( G [ c o m p ( i , i + d ) ] ) according to equation (16). 29  end 30  end 31 endIn the following theorem, we prove the correctness of Algorithm2 and analyze its time complexity.Theorem 13.
Algorithm2 outputs the isolated scattering number of an input interval graph on n vertices within time complexity O(n4).Proof.
The correctness of this algorithm follows from Theorem11 and Lemma 12. It is easy to see that the steps at lines 2–5 can be performed in O(1) time. The steps at lines 8–13 and 21–26 can be executed in time O(n4) in a straightforward manner. In the steps at lines 18–20, testing connectedness and computing the components can be done by O(n+m) algorithm for at most n2 graphs G[comp(i,j)]. If G[comp(i,j)] is disconnected and Qt is a component, then Qt=comp(it,jt), 1≤t≤k, can be computed in time O(n). Hence, the steps at lines 18–20 can be executed in time O(n4).
The steps at lines 15–17 have to be executed for at mostn3 triples (p,i,j) with i<p<j. If comp(i,j)∖C(αp)≠∅, then the components of G[comp(i,j)∖C(αp)] are computed as indicated in the proof of Lemma 12, by using the marks of (i,p) and (p,j); namely, if the mark is “complete” or “noncomplete”, then (i,p) and (p,j), respectively, are stored, and if the mark is “disconnected”, then the corresponding linked list is added. Thus the linked list of (p,i,j) can be computed in time O(n). Hence, the steps at lines 15–17 can be executed in time O(n4).
The steps at lines 27–29 require the evaluation of the right-hand side of (16) for at most n2 pairs (i,j). Each of the at most n values isc(G[Qi]) can be determined in constant time by table look-up, since the isolated scattering numbers of smaller pieces are already known. Thus (17)max⁡∑i=l+1tmax⁡iscwGQi,0-wCαp∩compi,j+lcan be evaluated in time O(n). Consequently, the steps at lines 27–29 of the algorithm can be executed in time O(n4). This completes the proof.


## 3. Conclusion

Network vulnerability is an important issue in the area of distributed computing. Sometimes it is important to incorporate subjective vulnerability estimates into the measure. In this paper, we introduce the weighted isolated scattering number to measure the vulnerability of weighed networks. We have proved that for interval graphs this parameter can be computed in polynomial time. For future work, it would be interesting for us to study the computational complexity for other graph classes such as chordal graphs, circular-arc graphs, and proper interval graphs.



---

*Source: 4318261-2019-03-10.xml*