Printer Friendly

Equivalent characterizations of some graph problems by covering-based rough sets.

1. Introduction

Covering is an extensively used form of data representation. As a generalization of classical rough set theory [1, 2], covering-based rough set theory [3, 4] was proposed to process this type of data. Due to its generality and universality, it has attracted much research interest. Covering reducts have been defined [5-9], approximation models [10-13] have been established, axiomatic systems [14-17] have been constructed, and generalization works [7, 18-21] have been conducted. In application, covering-based rough sets have been used in rule learning [22, 23], attribute reduction [24-26], feature selection [27, 28], and other fields [29-32].

Graphs are important discrete structures consisting of vertices and edges that connect these vertices, and they can well describe the relationship among objects. Problems in almost every discipline can be addressed using graph models. However, some important problems in graphs are NP-hard optimization ones such as finding the minimal vertex cover [33]and edge cover [34]. Therefore, it is much necessary to equivalently characterize these problems with other approaches or forms in order to find other efficient solutions.

In this paper, some graph concepts including vertex covers, independent sets, edge covers, and matchings are equivalently formulated using covering-based rough sets. First, a graph is represented with a covering, and an isomorphism from simple graphs without isolated vertices to a special type of coverings is constructed. Second, vertex covers, edge covers and matchings are equivalently described through the upper approximation number and independent sets with the lower approximation. Third, edge covers are also characterized by general reducts which are generalizations of the covering reduct. Furthermore, some graph problems are transformed into ones in covering-based rough sets. For instance, finding a minimal edge cover of a graph is equivalently converted to finding a minimal reduct of a covering.

There are numerous applications concerning connections between covering-based rough sets and graphs. For example, chemical classification, job assignment, and production process arrangement can be well modeled by graphs. However, many of these practical problems are NP-hard. Due to equivalent characterizations of covering-based rough sets and graphs, these problems can be converted and addressed under the framework of covering-based rough sets. In this way, heuristic reduction algorithms [5-8]for them maybe employed.

The rest of this paper is arranged as follows. Section 2 recalls some fundamentals related to covering-based rough sets and graph theory. In Section 3, the upper approximation number is presented, and its properties are studied. Section 4 represents graphs with coverings and establishes a one-to-one correspondence between a special type of coverings, and simple graphs without isolated vertices in an isomorphic sense. In Section 5, some important graph concepts including vertex covers, independent sets, edge covers, and matchings are formulated through the upper approximation number and lower approximation. Section 6 presents another equivalent characterization of edge covers by general reducts. In Section 7, this paper is concluded and further works are pointed out.

2. Basic Definitions

This section introduces some fundamental definitions related to covering-based rough sets and graphs.

2.1. Covering-Based Rough Sets. As a generalization of partitions, coverings are with strong applicability and high universality. For example, a course consists of a number of students, and all courses form a covering of all students. Since a student can choose several courses, the covering is not necessarily a partition of all students. All students compose the set of research objects, namely, universe of discourse.

Definition 1 (covering). Let U be a universe of discourse and C a family of subsets of U. If none of subsets in C is empty and [union] C = U, then C is called a covering of U.

Each subset in a covering is called a covering block also called a basic concept in knowledge discovery, and each subset of a universe is called a concept. An important idea of covering-based rough sets is to approximate a concept using some basic ones. This idea is implemented by a pair of lower and upper approximations.

Definition 2 (approximations [3]). Let C be a covering of U. For all X [subset] U,

[X.sub.*] = [union]{K [member of] C|K [subset] X}, [X.sup.*] = [union]{K [member of] C|K [intersection] X [not equal to] [empty set]} (1)

are called the lower and upper approximations of X (with respect to C), respectively.

The lower approximation provides a certainty, and the upper one offers a probability. If we suppose that the universe is all students selecting courses and the covering is the set of all courses, then for any subset of students, its lower approximation is those courses which all students select in the subset, and its upper approximation is those courses which some students select in the subset.

Some covering blocks may be redundant; in other words, removing them has little effect on the approximation accuracy. For example, if a course is a required one and all students must select it, then removing it does not affect the lower approximation. The concept of the reducible element was proposed to describe those redundant covering blocks.

Definition 3 (reducible element [35]). Let C be a covering of U and K [member of] C. K is called reducible in C if K can be expressed as a union of some elements in C -{K}; otherwise, K is irreducible. All irreducible elements of C are called the reduct of C, denoted as Reduct(C).

The reducible element well reveals the relationship between coverings and their lower approximations. In fact, two coverings generate the same lower approximation if and only if their reducts are the same.

2.2. Graphs. Graphs are discrete structures to model the correlation between data. Theoretically, a graph is an ordered pair consisting of vertices and edges that connect these vertices.

Definition 4 (graph [36]). A graph G = (V, E) consists of a nonempty set of vertices V and a set of edges E. Each edge has either one or two vertices associated with it, called its endpoints. Generally, we write e = uv or e = vu for an edge e with endpoints u and v.

The simple graph is a main research objective of graph theory, and many practical problems can be represented with a simple graph.

Definition 5 (simple graph [36]). A simple graph is a graph without loops or multiple edges, where a loop is an edge whose end points are equal and multiple edges are edges having the same pair of endpoints.

Graphs are visual and efficient tools to reveal the interrelation between data. Different graphs may have a certain internal relation. For this reason, isomorphism is introduced to express the relationship between graphs.

Definition 6 (isomorphism [36]). An isomorphism from one simple graph G = (V(G), E(G)) to another one H = (V(H), E(H)) is a bijection f : V(G) [right arrow] V(H) such that uv [member of] E(G) if and only if f(u)f(v) [member of] E(H).We say that G is isomorphic to H, denoted as G [equivalent to] H, if there exists an isomorphism from G to H.

In a graph that represents a road network (with straight roads and no isolated vertices), we can interpret the problem of finding the minimal vertex cover as the problem of placing the minimal number of policemen to guard the entire road network. It is noted that an isolated vertex of a graph is a vertex that is not an endpoint of any edge.

Definition 7 (vertex cover [36]). Let G = (V,E) be a graph. A vertex cover of G is a set Q [subset] V that contains at least one endpoint of any edge. The minimal size of vertex covers of G is denoted by [beta](G), simply by [beta].

Definition 8 (independent set [36]). Let G = (V,E) be a graph. An independent set of G is a set I [subset] V, and any two vertices of I are not adjacent. The maximal size of independent sets of G is denoted by a(G), simply by [alpha].

Definition 9 (edge cover [36]). Let G = (V, E) be a graph. L [subset] E is called an edge cover of G if for all v [member of] V, there exists [l.sub.v] [subset] L such that v is its endpoint. The minimal size of edge covers is denoted by [beta]'(G), simply by [beta]'.

Definition 10 (matching [36]). Let G = (V,E) be a graph. A matching M in G is a set of pairwise no-adjacent edges. A maximal matching is a matching M of a graph with the property that if any edge not in M is added to M, it is no longer a matching. The maximal size of matchings of G is denoted by [alpha]'(G), simply by [alpha]'. A perfect matching is a matching which matches all vertices of the graph.

3. The Upper Approximation Number of Covering-Based Rough Sets

Covering-based rough sets are studied qualitatively, and they are short of quantitative approaches. The following definition presents a measure to conduct the quantitative analysis. This measure is also a bridge between covering-based rough sets and graphs.

Definition 11 (upper approximation number [37, 38]). Let C be a covering of U. One can define, for all X [subset or equal to] U,

[f.sub.C](X) = [absolute value of ({K [member of] C |K [intersection] X [not equal to] [empty]})]. (2)

[f.sub.C](X) is called the upper approximation number of X and [f.sub.C], the upper approximation number function with respect to C. When there is no confusion, we omit the subscript C.

The above definition presents the upper approximation number with respect to a covering. Note that this concept can be defined similarly on any subcovering or family of subsets of a universe.

Example 12. Let U = {a, b, c, d}, [K.sub.1] = {a, b}, [K.sub.2] = {a, b, c}, [K.sub.3] = {c, d}, and C = {[K.sub.1], [K.sub.2], [K.sub.3]}. If X = {a, d} and Y = {c, d}, then f(X) = [absolute value of ({[K.sub.1], [K.sub.2], [K.sub.3]})] = 3 since [K.sub.1] [union] X [not equal to] 0, [K.sub.2] [intersection] X = 0, and [K.sub.3] [intersection] X [not equal to] 0. Similarly, f(Y) = 2.

The following proposition shows some properties of the upper approximation number and its connections with covering-based rough sets.

Proposition 13. Let C be a covering of U and f the upper approximation number function. Then the following properties hold for all X,Y cU,

(1) f([empty set]) = 0, f(U) = [absolute value of (C)],

(2) if X [subset] Y, then f(X) [less than or equal to] f(Y),

(3) for all u [subset] U, f({u}) [greater than or equal to] 1,

(4) f(X [union] Y) + f(X [intersection] Y) [less than or equal to] f(X) + f(Y).

When a covering is included in another one, their corresponding upper approximation numbers present a similar characteristic.

Proposition 14. Let [C.sub.1] and [C.sub.2] be two coverings of U. If [C.sub.1] [subset] [C.sub.2], then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (X) for all X [subset] U.

A partition can be equivalently characterized by the upper approximation number. A covering is a partition if and only if the upper approximation number of the set with only one element is equal to one.

Proposition 15. Let C be a covering of U. Then C is a partition of U if and only if f({u}) = 1 for all u [member of] U.

The upper approximation number plays an important role in both conducting quantitative analyses on covering based rough sets and building connections between them and graphs.

4. Graphs Represented with Coverings

In this section, we convert a graph to a covering in order to construct a platform for solving graph problems using covering-based rough sets. The following definition points out an approach to representing a simple graph with a family of subsets of vertices.

Definition 16. Let G = (V, E) be a simple graph. One can define a family F(G) of subsets of vertices of G as follows: for all x, y [member of] V,

{x, y} [member of] F (G) [??] xy [member of] E. (3)

According to Definition 16, a graph can be described with a family of subsets of its vertices. We say the family of subsets of vertices is induced by the graph. The following proposition presents the characteristics of the family of subsets of vertices.

Proposition 17. Let G = (V, E) be a simple graph. Then F(G) is a covering of V if and only if G has no isolated vertices.

Proof. ([??]): If F(G) is a covering of V, that is, [union] F(G) = V, then for all v [member of] V, there exists v' [member of] V such that {v, v} [member of] F(G); that is, vv' [member of] E. Hence, G has no isolated vertices.

([??]): If G has no isolated vertices, then for all v [member of] V, there exists v' [member of] V such that vv' [member of] E; that is, {v, v'} [member of] F(G). Thus, V = [[union].sub.v[member of]]V {v} [subset] [[union].sub.v[member of]V] {v, v'} [subset] [union]F(G) [subset] V. Hence, U F(G) = V; in other words, F(G) is a covering of V.

According to Proposition 17, a simple graph without isolated vertices can be characterized by a covering of its

vertices. Therefore, the family of the vertices induced by a graph is denoted by C(G). In fact, any edge subset of a graph can also be represented with a covering or a subcovering. For example, if S is an edge subset of a graph, then we can define C(S) as follows:

[for all]u, v [member of] V, {u, v} [member of] C (S) iff uv [member of] S. (4)

In the rest of this paper, a graph is a simple one without isolated vertices unless otherwise stated. The following example illustrates the graph and its covering.

Example 18. Let G = (V, E) be the graph as shown in Figure 1.Then C(G) = {{a, b},{a, d},{b, c},{b, e},{b, g},{c, h}, {c, f}, {d, g},{d, e},{e, h}, {e, f}}.

The following proposition explores the relationship between two graphs inducing the same covering. In fact, two different graphs induce the same covering if and only if they are isomorphic. Isomorphic graphs can be regarded as the same in graph theory. In other words, in an isomorphic sense, a one-to-one correspondence between coverings whose elements have only two objects and graphs is established.

Proposition 19. Let G, H be two graphs and C(G), C(H) the coverings induced by G, H. Then C(G) = C(H) if and only if G [equivalent to] H.

5. Graph Problems by the Upper Approximation Number

Independent sets, vertex covers, matchings, and edge covers of a graph are important concepts, and they stem abstractly from some practical problems. For instance, the maximal matching is from the job assignment problem. But some of them such as finding a minimal vertex cover are typical examples of NP-hard optimization problems. Therefore, there is much necessity to equivalently characterize these concepts. The following proposition presents a sufficient and necessary condition for the vertex cover through the upper approximation number.

Proposition 20. Let G = (V, E) be a graph and C(G) the covering induced by G and Q [subset or equal to] V. Then Q is a vertex cover of G if and only if [f.sub.C(G)](Q) = [absolute value of (C(G))].

Proof. ([??]): For all {x, y} [member of] C(G), according to Definition 16, xy [member of] E .Since Q [subset] V is a vertex cover of G, x [member of] Q or y [member of] Q which imply [f.sub.C(G)](Q) [greater than or equal to] [absolute value of (C(G))]. Conversely, [f.sub.C(G)](Q) [less than or equal to] [absolute value of (C(G))] is straightforward. To sum up, it proves that [f.sub.C(G)] (Q) = [absolute value of (C(G))].

([??]): Since [f.sub.C(G)](Q) = [absolute value of (C(G))], for all {x, y} [member of] C(G), x [member of] Q or y [member of] Q. According to Definition 16,for all xy [member of] E, x [member of] Q or y [member of] Q. Therefore, Q is a vertex cover of G.

In fact, in Proposition 20, [f.sub.C(G)](Q) = [absolute value of (C(G))] can be replaced with [f.sub.C{G)](Q) = [absolute value of (C(E))], since [absolute value of (C(G))] = [absolute value of (C(E))] for any graph, where [absolute value of (C(E))] denotes the number of edges. Therefore, based on the relationship between covering-based rough sets and graphs, a vertex cover of a graph can be described equivalently through the upper approximation number. Naturally, the minimal size of independent sets can also be represented by covering-based rough sets.

Proposition 21. Let G = (V, E) be a graph and [beta] the minimal size of vertex covers of G. Then [3 = min{[absolute value of (Q)] : [f.sub.C(G)](Q) = [absolute value of (C(E))]}.

Proof. According to Definition 7 and Proposition 20, it is straightforward.

The above proposition shows that finding a minimal vertex cover of a graph is equivalently transformed into finding a minimal subset whose upper approximation number is equal to the cardinality.

Example 22. Let G = (V,E) be the graph as shown in Figure 1. Suppose that Q = {b, d, f, h}, then [f.sub.C](G)(Q) = [absolute value of (C(E))]. For all Q' [subset] V and [absolute value of (Q')] < [absolute value of (Q)], [f.sub.C{G)](Q') < [absolute value of (C(G))]. Then the minimal vertex cover is [beta] = [absolute value of (Q)] = 4, and a maximal vertex cover is presented in Figure 2.

The following proposition indicates that an independent set of a graph can also be formulated equivalently with the lower approximation operator. In fact, a subset of vertices of a graph is an independent set if and only if its lower approximation is empty.

Proposition 23. Let G = (V, E) be a graph and I [subset] V. Then I is an independent set of G if and only if [I.sub.*] = 0 where [I.sub.*] = [union]{K [member of] C(G)|K [subset] I}.

Proof. ([??]): Since I is an independent set of G, any two vertices of I are not adjacent which implies that {x, y} [intersection] I [not equal to] {x, y},for all xy [member of] E .Hence, [I.sub.*] = [empty set].

([??]): Since [I.sub.*] = [empty set], then {x, y} [intersection] I [not equal to] {x, y}, which implies that no two elements of I are adjacent. Hence, I is an independent set of G.

Proposition 24. Let G = (V, E) be a graph and [alpha] the maximal size of independent sets. Then [alpha] = max{[absolute value of (I)] : I [subset] V, and [I.sub.*] = [empty set]}.

Proof. According to Definition 8 and Proposition 23, it is straightforward.

The above proposition indicates that finding a maximal independent set is converted to finding a maximal subset keeping its lower approximation empty. The following example illustrates independent sets of a graph and its connection with the lower approximation.

Example 25. Let G = (V, E) be the graph as shown in Figure 1. Suppose that I = {a, c, e, g}, then I* =0. For all I' [subset] V and [absolute value of (I')] > [absolute value of (I)], [I.sub.*] = [empty set]. Then the maximal size of independent sets is [alpha] = [absolute value of (I)] = 4, and a maximal independent set is presented in Figure 3.

A matching of a graph can also be represented with the upper approximation number. In fact, an edge subset of the edges of a graph is a matching if and only if the upper approximation number of these sets having only one element is not less than one.

Proposition 26. Let G = (V, E) be a graph and M [subset] E. Then M is a matching of G if and only if [f.sub.C(M)]({v}) [less than or equal to] 1 for all v [member of] V.

Furthermore, the perfect matching of a graph is concisely characterized by the upper approximation number.

Proposition 27. Let G = (V, E) be a graph and M [subset] E. Then M is a perfect matching of G if and only if [f.sub.C(M)]({v}) = 1 for all v [member of] V.

Proposition 28. Let G = (V, E) be a graph and [alpha]' the maximal size of matchings of G. Then [alpha]' = max{[absolute value of (M)] : M [subset] E and [f.sub.C(M)]({v}) [less than or equal to] 1 for all v [member of] V}.

Example 29. Let G = (V, E) be the graph as shown in Figure 1.Suppose that M = {ab, cf, dg, eh}, then C(M) = {{a, b}, {c, f}, {d, g}, {e, h}}. Therefore, M is a maximal matching of G since [f.sub.C(M)]({v}) [less than or equal to] 1 for all v [member of] V. In fact, it is also a perfect matching. The matching is presented in Figure 4.

Proposition 30. Let G = (V, E) be a graph and L [subset] E. Then L is an edge cover of G if and only if [f.sub.C(L)]({v}) [greater than or equal to] 1 for all v [member of] V.

Proof. ([??]): If L is an edge cover of G, then for all v [member of] V, there exists v' [member of] V such that vv' [member of] E, that is, {v, v' [member of] C(L). Hence, [f.sub.C(L)]({v}) [greater than or equal to] 1.

([??]): If for all v [member of] V, [f.sub.C(L)]({v}) [greater than or equal to] 1, then there exists v' [member of] V such that {v, v} [member of] C(L); that is, vv' [member of] E. Thus, L is an edge cover of G.

Proposition 31. Let G = (V, E) be a graph and f> the minimal size of edge covers of G. Then [beta]' = min{[absolute value of (L)] : L [subset] E and [f.sub.C(L)]({v}) [greater than or equal to] 1 for all v [member of] V}.

6. Graph Problems by General Reduct

This section presents another view to represent graph problems with covering-based rough sets. First of all, we define the generally reducible element of a covering, which is an extension of the reducible element in the literature [35].

6.1. General Reduct. Pawlak defined category reducts for knowledge reduction and rule extraction [39]. Zhu and Wang [35] proposed the reducible element to remove the redundancy and keep the essence. Some forms of reducible elements are defined and applied to rule learning [6]and other fields [12, 14]. The following definition proposes generally reducible elements to characterize graph concepts including edge covers and matchings.

Definition 32 (generally reducible element). Let C be a covering of U and K [member of] C. K is called a generally reducible element in C if C -{K} is also a covering of U; otherwise, K is called a generally irreducible element.

Definition 33 (general reduct). Let C be a covering of U and C' [subset] C. C' is called a general reduct of C, if [union] C = U and for all K' [member of] C', K' is a generally irreducible element of C'.

Example 34. Let U = {a, b, c, d} and C = {[K.sub.1], [K.sub.2], [K.sub.3], [K.sub.4]}, where [K.sub.1] = {a, b}, [K.sub.2] = {a, c}, [K.sub.3] = {a, b, c}, and [K.sub.4] = {d}. Then [K.sub.1], [K.sub.2] and [K.sub.3] are generally reducible elements of C; however, [K.sub.1] and [K.sub.2] are irreducible elements of C. And [C.sub.1] = {[K.sub.1], [K.sub.2], [K.sub.4]} and [C.sub.2] = {[K.sub.3], [K.sub.4]} are general reducts of C.

The following proposition shows that the generally reducible element is an extension of the reducible element. In other words, if a covering block is reducible, then it is generally reducible.

Proposition 35. Let C be a covering of U and K [member of] C. If K is a reducible element of C, then K is a generally reducible element of C.

Remark 36. The generally reducible element is an extension of the reducible element; however, the general reduct is not an extension of the reduct. The following counterexample illustrates this argument.

Let U = {a, b, c} and C = {[K.sub.1], [K.sub.2], [K.sub.3]} where [K.sub.1] = {a, b}, [K.sub.2] = {b, c}, and [K.sub.3] = {a, c}. Therefore, Reduct(C) = C; however, Reduct(C) is not a general reduct of C. In fact, the general reducts of C are [C.sub.1] = {[K.sub.1], [K.sub.2]}, [C.sub.2] = {[K.sub.1], [K.sub.3]}, and [C.sub.3] = {[K.sub.2], [K.sub.3]}.

6.2. Equivalent Characterization of Graph Problems by General Reducts. The following proposition explores the relationship between general reducts and edge covers of a graph. In fact, an edge subset of a graph is an edge cover if and only if it contains at least one general reduct.

Proposition 37. Let G = (V, E) be a graph and L [subset] E. L is an edge cover of G if and only if there exists a general reduct G of C(G) such that G [subset] C(L).

Proof. ([??]): If L [subset] E is an edge cover, then for all v [member of] V, there exists [l.sub.v] = vv' [member of] L, such that v is its endpoint. This proves for all v [member of] V that there exists v' [member of] V such that {v, v'} [member of] C(L).Thus, V = [[union].sub.v[member of]V],{v} [subset] [[union].sub.v[member of]V] {v, v'} [subset] [union] C(L) [subset] V. Then, [union]C(L) = V. Hence, there exists G [subset] C(L), such that G is a general reduct of C(L).So G is also a general reduct of C(G). Therefore, there exists a general reduct of G of C(G) such that G [subset] C(L).

([??]): If there exists a general reduct G of C(G) such that G [subset] C(L), then C(L) is a covering of V. Hence, for all v [member of] V, there exists v [member of] V, such that {v, v'} [member of] C(L); that is, vv' [member of] L. Hence, v is an endpoint of [l.sub.v] = vv'. Therefore, L is an edge cover of G.

According to Proposition 37, edge covers of a graph can be characterized by general reducts. In other words, finding a minimal edge cover of a graph is transformed equivalently into finding a minimal reduct of a covering.

Proposition 38. Let G = (V, E) be a graph. Then [beta]' = min{[absolute value of (G)]: G is a general reduct of C(G)}.

Proof. According to Proposition 37, it is straightforward.

Matchings of a graph can also be described using the generally reducible element.

Proposition 39. Let G = (V, E) be a graph and M [subset] E. If M is a matching of G, then for all K [subset] C(M), K is a generally reducible element of C(G).

Proposition 39 shows a necessary condition for a matching of a graph by the generally reducible element. The following proposition further presents the characteristic of matchings using covering-based rough sets. In fact, an edge subset is a matching if and only if there exists an order such that those elements in the set can be reducible one by one according to the order.

Proposition 40. Let G = (V, E) be a graph, M [subset] E, and [absolute value of (M)] = m. Then M is a matching of G if and only if there is a permutation of elements of C(M) such that [K.sub.i] [member of] C(M) is a generally reducible element of C(G) - {[K.sub.1], ..., [K.sub.i-1]} for i = 1, ..., m.

7. Conclusions and Further Works

In this paper, we presented equivalent characterizations for some important problems in graph theory from the viewpoint of covering-based rough sets. These problems included vertex covers, independent sets, edge covers, and matchings of a graph, where finding a minimal vertex cover was NP-hard. The equivalent characterizations indicated covering-based rough sets approaches to these problems. Moreover, graph concepts such as vertex connectivity and graph approaches such as shortest path algorithms were available to study covering-based rough sets. In future works, we will apply these interesting theoretical results not only to algorithm design for some graph problems but also to unsupervised learning, especially bipartite graph clustering and spectral clustering.

http://dx.doi.org/10.1155/2013/519173

Acknowledgments

This work is supported in part by the National Natural Science Foundation of China under Grant no. 61170128, the Natural Science Foundation of Fujian Province, China, under Grants nos. 2011J01374 and 2012J01294, and the Science and Technology Key Project of Fujian Province, China, under Grant no. 2012H0043.

References

[1] T. B. Iwhiski, "Algebraic approach to rough sets," Bulletin of the Polish Academy of Sciences, vol. 35, no. 9-10, pp. 673-683, 1987.

[2] Z. Pawlak, "Rough sets," International Journal of Computer and Information Sciences, vol. 11, no. 5, pp. 341-356, 1982.

[3] W. Zakowski, "Approximations in the space (u, n)"' Demonstratio Mathematica, vol. 16, no. 3, pp. 761-769, 1983.

[4] W. Zhu, "Relationship among basic concepts in covering-based rough sets," Information Sciences, vol. 179, no. 14, pp. 2478-2486, 2009.

[5] C. Degang, W. Changzhong, and H. Qinghua, "A new approach to attribute reduction of consistent and inconsistent covering decision systems with covering rough sets," Information Sciences, vol. 177, no. 17, pp. 3500-3518, 2007.

[6] Y. Du, Q. Hu, P. Zhu, and P. Ma, "Rule learning for classification based on neighborhood covering reduction," Information Sciences, vol. 181, no. 24, pp. 5457-5467, 2011.

[7] R. Jensen and Q. Shen, "Semantics-preserving dimensionality reduction: rough and fuzzy-rough-based approaches," IEEE Transactions on Knowledge and Data Engineering, vol. 16, no. 12, pp. 1457-1471, 2004.

[8] F. Min, H. He, Y. Qian, and W. Zhu, "Test-cost-sensitive attribute reduction," Information Sciences, vol. 181, pp. 4928 4942, 2011.

[9] T. Yang and Q. Li, "Reduction about approximation spaces of covering generalized rough sets," International Journal of Approximate Reasoning, vol. 51, no. 3, pp. 335-345, 2010.

[10] C. Bazgan, J. Monnot, V. Th. Paschos, and F. Serriere, "On the differential approximation of MIN SET COVER," Theoretical Computer Science, vol. 332, no. 1-3, pp. 497-513, 2005.

[11] A. Skowron, J. Stepaniuk, and R. Swiniarski, "Modeling rough granular computing based on approximation spaces," Information Sciences, vol. 184, pp. 20-43, 2012.

[12] Y. Yao and B. Yao, "Covering based rough set approximations," Information Sciences, vol. 200, pp. 91-107, 2012.

[13] W. Zhu and F. Y. Wang, "On three types of covering-based rough sets," IEEE Transactions on Knowledge and Data Engineering, vol. 19, no. 8, pp. 1131-1143, 2007.

[14] S. Wang, W. Zhu, Q. Zhu, and F. Min, "Covering base," Journal of Information and Computational Science, vol. 9, pp. 1343-1355, 2012.

[15] P. Zhu, "An axiomatic approach to the roughness measure of rough sets," Fundamental Informaticae, vol. 109, no. 4, pp. 463 480, 2011.

[16] W. Zhu, "Topological approaches to covering rough sets," Information Sciences, vol. 177, no. 6, pp. 1499-1508, 2007.

[17] W. Zhu, "Relationship between generalized rough sets based on binary relation and covering," Information Sciences, vol. 179, no. 3, pp. 210-225, 2009.

[18] T. Deng, Y. Chen, W. Xu, and Q. Dai, "A novel approach to fuzzy rough sets based on a fuzzy covering," Information Sciences, vol. 177, no. 11, pp. 2308-2326, 2007.

[19] D. Dubois and H. Prade, "Rough fuzzy sets and fuzzy rough sets," International Journal of General Systems, vol.17, pp.191 209, 1990.

[20] Q. He, C. Wu, D. Chen, and S. Zhao, "Fuzzy rough set based attribute reduction for information systems with fuzzy decisions," Knowledge-Based Systems, vol. 24, no. 5, pp. 689-696, 2011.

[21] G. Liu, "Generalized rough sets over fuzzy lattices," Information Sciences, vol. 178, no. 6, pp. 1651-1662, 2008.

[22] M. Kryszkiewicz, "Rules in incomplete information systems," Information Sciences, vol. 113, no. 3-4, pp. 271-292, 1999.

[23] S. K. Pal, S. Mitra, and P. Mitra, "Rough-fuzzy MLP: modular evolution, rule generation, and evaluation," IEEE Transactions on Knowledge and Data Engineering, vol. 15, no. 1, pp. 14-25, 2003.

[24] Q. Hu, J. Liu, and D. Yu, "Mixed features election based on granulation and approximation," Knowledge-Based Systems, vol. 21, pp 294-304, 2007

[25] F. Min and Q. Liu, "A hierarchical model for test-cost-sensitive decision systems," Information Sciences, vol. 179, no. 14, pp. 2442-2452, 2009.

[26] F. Min and W. Zhu, "Attribute reduction of data with error ranges and test costs," Information Sciences, vol. 211, pp. 48-67, 2012.

[27] Y. Chen, D. Miao, R. Wang, and K. Wu, "A rough set approach to feature selection based on power set tree," Knowledge-Based Systems, vol. 24, no. 2, pp. 275-281, 2011.

[28] Q. Hu, D. Yu, J. Liu, and C. Wu, "Neighborhood roughset based heterogeneous feature subset selection," Information Sciences, vol. 178, no. 18, pp. 3577-3594, 2008.

[29] J. Dai, W. Wang, Q. Xu, and H. Tian, "Uncertainty measurement for interval-valued decision systems based on extended conditional entropy," Knowledge-Based Systems, vol. 27, pp. 443-450, 2012.

[30] C. Wang, D. Chen, C. Wu, and Q. Hu, "Data compression with homomorphism in covering information systems," International Journal of Approximate Reasoning, vol. 52, no. 4, pp. 519-525, 2011.

[31] S. Wang, Q. Zhu, W. Zhu, and F. Min, "Matroidal structure of rough sets and its characterization to attribute reduction," Knowledge-Based Systems, vol. 36, pp. 155-161, 2012.

[32] Y. Yao, "The superiority of three-way decisions in probabilistic rough set models," Information Sciences, vol. 181, no. 6, pp. 1080 1096, 2011.

[33] J. Chen, I. A. Kanj, and W. Jia, "Vertex cover: further observations and further improvements," Journal of Algorithms, vol. 41, no. 2, pp. 280-301, 2001.

[34] F. Gomory, "Improvement of the self-field critical current of a high-tc superconducting tape by the edge cover from soft ferromagnetic material," Applied Physics Letters, vol. 89, no. 7, Article ID 072506, 2006.

[35] W. Zhu and F.-Y. Wang, "Reduction and axiomization of covering generalized rough sets," Information Sciences, vol. 152, pp. 217-230, 2003.

[36] D. B. West, Introduction To Graph Theory, Pearson Education, 2002.

[37] S. Wang and W. Zhu, "Matroidal structure of covering-based rough sets through the upper approximation number," International Journal of Granular Computing, Rough Sets and Intelligent Systems, vol. 2, pp. 141-148, 2011.

[38] W. Zhu and S. Wang, "Matroidal approaches to generalized rough sets based on relations," International Journal of Machine Learning and Cybernetics, vol. 2, pp. 273-279, 2011.

[39] Z. Pawlak, Rough Sets: Theoretical Aspects of Reasoning About Data, Kluwer Academic Publishers, Boston, Mass, USA, 1991.

Shiping Wang, (1) Qingxin Zhu, (1) William Zhu, (2) and Fan Min (2)

(1) School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 611731, China

(2) Lab of Granular Computing, MinnanNormal University, Zhangzhou, Fujian363000, China

Correspondence should be addressed to William Zhu; williamfengzhu@gmail.com

Received 4 January 2013; Accepted 30 April 2013

Academic Editor: Hector Pomares
COPYRIGHT 2013 Hindawi Limited
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2013 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:Research Article
Author:Wang, Shiping; Zhu, Qingxin; Zhu, William; Min, Fan
Publication:Journal of Applied Mathematics
Article Type:Report
Date:Jan 1, 2013
Words:5943
Previous Article:Peaked and smooth solitons for [K.sup.*](4, 1) equation.
Next Article:Synchronization of chaotic gyros based on robust nonlinear dynamic inversion.
Topics:

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters