China 
Africa 
Explore chapters and articles related to this topic
Dominating Set Theory and Algorithms
Published in Jiguo Yu, Xiuzhen Cheng, Honglu Jiang, Dongxiao Yu, Hierarchical Topology Control for Wireless Networks, 2018
Jiguo Yu, Xiuzhen Cheng, Honglu Jiang, Dongxiao Yu
This section will introduce the DP algorithm with linear time proposed in Reference [72]. First, we give the definition of the interval graph. In graph theory, interval graph is an intersected graph of multiple interval sets, in which each interval corresponds to a vertex in the graph. If two intervals are intersected, there is an edge between the two nodes, as shown in Figure 4.27.
On some inverse 1-center location problems
Published in Optimization, 2019
Kien Trung Nguyen, Nguyen Thanh Hung, Huong Nguyen-Thu, Tran Thu Le, Van Huy Pham
An interval graph is, by definition, the intersection graph of a family of intervals on the real line. Roughly speaking, each interval represents a vertex, say in V , for . Moreover, if , there exists an edge in E for . For applications of interval graphs, e.g. genetic structure, sequential storage, scheduling, seriation in archaeology, etc., one can see Golumbic [23] and references therein. We further assume that all edges of G have the length of 1 and each vertex is associated with a positive weight for . The interval graph G is connected if for any interval I there exists at least one interval which has nonempty intersection with I in the presentation of G. Moreover, a proper interval graph is an interval graph that has an interval representation in which no interval is properly contained in another interval. A proper interval graph can be recognized in linear time by Panda and Das [24]. From here after, we always assume that G is a proper connected interval graph. For illustration, we can observe a proper connected interval graph in Figure 1 which is presented by a class of intervals on the line as in Figure 2.