(ProQuest: ... denotes non-US-ASCII text omitted.)
Academic Editor:Yuri N. Sotskov
School of Mathematics, Shandong University, Jinan 250100, China
Received 10 January 2014; Accepted 21 March 2014; 28 April 2014
This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
1. Introduction
A hypergraph H=(V,...) is composed of a finite set V and a collection ... of nonempty subsets of V , in which V is called the vertex set of H and ... is called the edge set of H . Thus, graphs are a special kind of hypergraphs with two vertices in each edge. One of the basic problems about hypergraph theory is the stable set problem, which has been widely applied in many research fields like network coding [1, 2]. Another basic problem about hypergraph theory is the coloring problem, which is one of NP-complete problems. There are various forms of hypergraph coloring such as vertex coloring, good coloring of edges, strong coloring, and equitable coloring. Graph coloring has been widely used in many real-life areas including scheduling and timetabling in engineering, register allocation in compilers, and air traffic flow management and frequency assignment in mobile [3-6]. The coloring problems of a special kind of graphs have been widely discussed in [7-9]. In recent years, there have been some references considering hypergraph theory, such as [10, 11]. It has been successfully applied to many different areas such as Markov decision process [12], complete simple games [13], linear programming [14], and cooperation structures in games [15]. And a few references have analyzed the colorability of different kinds of hypergraphs [16-18]. However, there are no proper algebraic algorithms for stable set and coloring problems of hypergraphs. Thus, they are still open problems and it is necessary for us to establish new formulations and algorithms.
In recent years, Cheng et al. [19, 20] have proposed an effective tool, called the semitensor product (STP) of matrices. Via STP, Boolean networks can be converted into an algebraic form and many problems of Boolean networks, such as controllability and observability [21], fixed points and cycles [22], and control design problems [23-25], have been investigated. To learn more about the applications of STP, the readers can refer to [26-30].
In this paper, we investigate the stable set and vertex coloring problems of hypergraphs and present some new results and algorithms via STP. By incidence matrix and characteristic logical vector (CLV), a necessary and sufficient condition, as well as a new algorithm, is established for hypergraph stable sets. Then, we study the vertex coloring problem. An algebraic equivalent condition and an algorithm for coloring problem are obtained. With the two algorithms, we can calculate all the stable sets and coloring schemes with the given q colors for any hypergraph. The results we obtained in this paper are feasible and clear, illustrated by an example and a practical application to the storing problems. Compared to [31], which has considered the stable set and coloring problems of graphs by STP, the results we obtained seem to be the generalization of [31]. However, just applying the results about graphs in [31] to hypergraphs, we cannot get the similar results about hypergraphs. In fact, there are many differences. We use incidence matrix of hypergraphs, while Wang et al. in [31] have used adjacent matrix of graphs. The derivations are completely different since the fundamental techniques used are not the same. Thus, in our paper, the results are new and innovative in some ways.
The remainder of this paper is organized as follows. Section 2 introduces the preliminaries on STP and hypergraph theory. In Sections 3 and 4, we investigate the stable set and coloring problems, respectively, and provide the main results and algorithms of this paper. One illustrative example is also given in Section 3, and the application of coloring problem to storing problem is presented in Section 5 to show the effectiveness and applicability of the obtained results. Section 6 makes a brief conclusion.
Before ending this section, we introduce some notations which will be used throughout this paper. Consider the following.
(i) [physics M-matrix]m×n is the set of m×n real matrices.
(ii) δni is the i th column of the identity matrix In .
(iii): Δn :={δni |"i=1,...,n} . Δ2 :=Δ .
(iv) ...9F;:={0,1} . Identify 1~δ21 , 0~δ22 ; then, ...9F;~Δ .
(v) A∈[physics M-matrix]m×n is called a Boolean matrix, if all its entries are either 0 or 1. The set of m×n Boolean matrices is denoted by [Bernoulli]m×n .
(vi) A matrix L∈[physics M-matrix]n×r is called a logical matrix if the columns of L , denoted by Col(L) , belong to Δn . That is, Col(L)⊆Δn . And Coli (L) means the i th column of L . Denote the set of n×r logical matrices by [Lagrangian (script capital L)]n×r .
(vii): If L∈[Lagrangian (script capital L)]n×r , by definition it can be expressed as L=[δni1δni2 ...δnir ] . Briefly, we denote it by L=δn [i1i2 ...ir ] .
(viii): For A=(aij ) , B=(bij )∈[physics M-matrix]m×n , A...5;...5;(...4;...4;,...b;,...a;)B means aij ...5;(...4;,>,<)bij , for all i,j .
(ix) For a set S , |S| is the cardinality of S .
(x) A=Diag{A1 ,A2 ,...,Ar } is a block-diagonal matrix with Ai in the (i,i) th position (1...4;i...4;r) .
(xi) Let A=(aij )∈[physics M-matrix]m×n , B∈[physics M-matrix]p×q . The Kronecker product of matrices A and B is defined as [figure omitted; refer to PDF]
2. Preliminaries
In this section, we will give some necessary preliminaries on STP and hypergraph theory, which will be used later.
Definition 1 (see [20]).
Let A∈[physics M-matrix]m×n and B∈[physics M-matrix]p×q . The STP of matrices A and B , denoted by A[x, left closed]B , is defined as [figure omitted; refer to PDF] where s=lcm{n,p} is the least common multiple of n and p .
Remark 2.
When n=p , STP coincides with conventional matrix product. So STP is a general form of matrix product. Throughout this paper, the matrix product is assumed to be STP, and the symbol "[x, left closed] " is omitted if there is no confusion.
Definition 3 (see [19]).
A swap matrix W[m,n] is an mn×mn matrix, defined as follows: label its columns by (11,12,...,1n,...,m1,m2,...,mn) ; label its rows by (11,21,...,m1,...,1n,2n,...,mn) , and then the element at the position [(I,J),(i,j)] is [figure omitted; refer to PDF]
Definition 4 (see [32]).
Let A=(aij ) , B=(bij )∈[physics M-matrix]m×n . The Hadamard product of A and B is defined as [figure omitted; refer to PDF]
Lemma 5 (see [19]).
( 1 ) Let X∈...m and Y∈...n be two column vectors. Then, [figure omitted; refer to PDF]
( 2 ) Given A∈[physics M-matrix]m×n , let Z∈...t be a column vector. Then, [figure omitted; refer to PDF]
( 3 ) Let X∈...n , Y∈...q be two column vectors and let A∈[physics M-matrix]m×n , B∈[physics M-matrix]p×q be two given matrices. Then, [figure omitted; refer to PDF]
( 4 ) Let f(x1 ,x2 ,...,xr ) be a Boolean function. Then, there exists a unique logical matrix Lf ∈[Lagrangian (script capital L)]2×2r such that [figure omitted; refer to PDF] Here, Lf ∈[Lagrangian (script capital L)]2×2r is called the structure matrix of f .
Now, some structure matrices of basic logical operators are given as follows: [figure omitted; refer to PDF] And the power reducing matrix is defined as [figure omitted; refer to PDF] Then, if X,Y∈Δ , we will have X⋁Y=Md XY , X⋀Y=Mc XY , ¬X=Mn X , X[arrow right]Y=Mi XY , and X[x, left closed]X=Mr X .
Definition 6 (see [33]).
Let V={v1 ,v2 ,...,vn } be a finite set, and let ...={E1 ,E2 ,...,Em } be a family of subsets of V ; that is, Ej ⊆V , j=1,2,...,m . The family ... is said to be a hypergraph on V denoted by H=(V,...) , if Ej ...0;... , j=1,2,...,m , and ...j=1mEj =V . The elements v1 ,v2 ,...,vn are called the vertices (hypervertices) and the sets E1 ,E2 ,...,Em are called the edges (hyperedges).
The incidence matrix of hypergraph H=(V,...) is a matrix A=(aij ) with m rows that represent the edges of H and n columns that represent the vertices of H , such that [figure omitted; refer to PDF]
Definition 7 (see [33]).
Given a hypergraph H=(V,...) , a set S⊆V is called a stable set if it contains no edge Ei with |Ei |>1 . Furthermore, S is called a maximum stable set, if any vertex subset strictly containing S is not a stable set. A stable set S is called an absolutely maximum stable set if |S| is the largest among all of the stable sets of H . The stable number of H , denoted by α(H) , is defined to be the maximum cardinality of all the stable sets of H .
Remark 8.
For a hypergraph H=(V,...) , any subset of stable set S is a stable set. If there exists Ei ∈... satisfying |Ei |=1 , that is, H has an edge formed by an isolated vertex, then, all the stable sets of H can be obtained from all the stable sets of H[variant prime] =(V[variant prime] ,...[variant prime] ) where ...[variant prime] =...-{Ei } . In fact, if all the stable sets of H[variant prime] are S1 ,...,Sr , then, all the stable sets of H are S1 ,...,Sr ,S1 ∪{Ei },...,Sr ∪{Ei } . Therefore, in this paper, we just consider the edges of cardinality more than one. Additionally, the empty set ... is regarded as a stable set of any hypergraph.
Definition 9 (see [33]).
A q -coloring is defined to be a partition of V into q stable sets S1 ,S2 ,...,Sq , each corresponding to a color. A hypergraph for which there exists a q -coloring is said to be q -colorable.
3. Stable Set Problem
In the section, we investigate the stable set problem of hypergraphs using the STP method and present algebraic equivalent conditions, as well as an algorithm.
Given a hypergraph H=(V,...) with n vertices V={v1 ,v2 ,...,vn } and m edges ...={E1 ,E2 ,...,Em } , assume that the incidence matrix of H is A=(aij)m×n . Denote the i th row of A by ai , i=1,2,...,m ; then A=[a1T ,a2T ,...,amT ]T . Assume that S is a subset of V . Then, in the following, we will discuss under what conditions the subset S is a stable set. First, we define some vectors.
The CLV of S , denoted by VS =[x1 ,x2 ,...,xn ] , is denoted as [figure omitted; refer to PDF] And then denote [figure omitted; refer to PDF] It is easy to see that VS is a Boolean vector and yij ,yj ∈Δ . Then, we can present the following results.
Theorem 10.
Consider the hypergraph H=(V,...) expressed as above. Then S is a stable set of H if and only if the last row of matrix M¯ has at least one zero element, where [figure omitted; refer to PDF]
Proof.
Let E-l =El \S with the CLV a¯l =[a¯l1 ,a¯l2 ,...,a¯ln ] , l=1,2,...,m . Denote [figure omitted; refer to PDF] Then, S is a stable set if and only if, for every l∈{1,2,...,m},E¯l ...0;... ; that is, a¯l ...0;01×n . Since a¯l ...0;01×n if and only if [x, left closed]t=1ny¯lt ...0;δ2n2n if and only if the last element of [x, left closed]t=1ny¯lt is 0, we just need to prove that, for every l∈{1,2,...,m} , the last element of [x, left closed]t=1ny¯lt is 0 if and only if the last row of matrix M¯ has one zero component at least.
Let J1T =δ2n2n . If, for every l∈{1,2,...,m} , the last element of [x, left closed]t=1ny¯lt is 0, then, we get, for every l,J1[x, left closed]t=1ny¯lt =0 . Thus, y¯lt satisfies [figure omitted; refer to PDF] Since E-l =El \S , a¯lt =alt -alt ⋀xt . Hence, [figure omitted; refer to PDF] So (16) can be expressed as [figure omitted; refer to PDF] By Lemma 5, we have [figure omitted; refer to PDF] where Y=[x, left closed]t=1nyt ∈Δ2n and Yl is described in (14). Therefore, (16) becomes [figure omitted; refer to PDF] That is, [figure omitted; refer to PDF] Noticing that Y∈Δ2n , we have that (21) having a solution Y is equivalent to the last row of M¯ having one zero element at least. The necessity is proved.
On the other hand, if the last row of M¯ has one zero element at least, then the equation J1 M¯Y=0 has a solution Y∈Δ2n . Equivalently, (16) holds. Noticing that J1[x, left closed]t=1ny¯lt ...5;0 , from (16) we obtain J1[x, left closed]t=1ny¯lt =0 ; that is, for every l∈{1,2,...,m} , the last element of [x, left closed]t=1ny¯lt is 0. Hence the proof is completed.
From the above theorem, we find that (21) plays an important role to calculate all the stable sets of hypergraph H . The following corollary shows the relationship between (21) and the stable sets of hypergraphs.
Corollary 11.
Consider the hypergraph H in Theorem 10. H has a stable set if and only if (21) has a solution Y=[x, left closed]t=1nyt ∈Δ2n . In addition, the number of stable sets of H is the cardinal of solution set of (21).
In order to obtain all the stable sets of any hypergraph, we will give an algorithm according to the proof of Theorem 10 and the results of Corollary 11.
Algorithm 12.
Consider a hypergraph H shown in Theorem 10. The following steps are given to find all the stable sets of H .
(1) Calculate the matrix M¯ given in (14).
(2) Denote the last row of M¯ by β=[b1 ,b2 ,...,b2n ] . If bi ...0;0 , for every i∈{1,2,...,2n } , then, H has no stable set and stop. Otherwise, find out all the zero elements of β : bi1 =bi2 =...=bip =0 . Then, bik =0 corresponds to a solution, Y=δ2nik , of (21) and so does a stable set of H .
(3) From [x, left closed]j=1nyj =δ2nik , we can retrieve yt as yt =Stn[x, left closed]j=1nyj =Stnδ2nik , t=1,2,...,n , where Stn , t=1,2,...,n are defined as follows [19]: [figure omitted; refer to PDF] By the definition of (12), we obtain the stable set corresponding to δ2nik : [figure omitted; refer to PDF] Thus, all the stable sets of H are {S(ik )|"k=1,2,...,p} .
Remark 13.
From Algorithm 12, we can obtain all the stable sets of hypergraph H ; therefore, the absolutely maximum stable sets can also be determined. Denote the stable number of H by α0 ; then, α0 =max1...4;k...4;p {|S(ik )|} , and all the absolutely maximum stable sets can be derived as S={S(ik )|"|S(ik )|=α0 } .
Remark 14.
Although the calculation of the above algorithm is complex, the advantage of this approach is that we can obtain all the stable sets as well as all the absolutely maximum stable sets of a hypergraph. And we can turn to the computer using MATLAB toolbox.
Example 15.
Consider the hypergraph H=(V,...) , where V={v1 ,v2 ,v3 ,v4 ,v5 } , ...={E1 ,E2 ,E3 ,E4 } , E1 ={v1 ,v2 ,v3 } , E2 ={v3 ,v4 ,v5 } , E3 ={v2 ,v3 ,v4 } , and E4 ={v2 ,v4 ,v5 } . In the following, we use Algorithm 12 to find all the stable sets of the hypergraph.
By the definition of the incidence matrix of the hypergraph H , the incidence matrix of H is [figure omitted; refer to PDF] By MATLAB toolbox, we easily get [figure omitted; refer to PDF] Thus, [figure omitted; refer to PDF] Then, we obtain the last row of M¯ as [figure omitted; refer to PDF] and the indexes of zero elements in β are [figure omitted; refer to PDF] For each index ik ∈P , let [x, left closed]i=15yi =δ25ik . Via computing yi =Si5δ25ik , i=1,2,...,5 , we have all the stable sets of H as follows: [figure omitted; refer to PDF]
Therefore, from the calculation results, we know maxik {|Sik |}=3 ; all the absolutely maximum stable sets are {S1 ,S2 ,S4 ,S5 ,S7 ,S11 } .
4. Coloring Problem
In this section, we study the vertex coloring problem of hypergraphs, that is, given q colors, how to color the vertices of the hypergraph H such that no edge has all its vertices with the same color.
Consider a hypergraph H=(V,...) , with V={v1 ,v2 ,...,vn } , ...={E1 ,E2 ,...,Em } , and assume that its incidence matrix is A=(aij )∈[Bernoulli]m×n . Given q kinds of colors: c1 ,c2 ,...,cq , let N={c1 ,c2 ,...,cq } be the color set; then, we can define a mapping [varphi]:V...N . Since all of the q colors may not be used, [varphi] may not be a surjective. To solve the coloring problem of hypergraph H , we can just find a mapping [varphi] satisfying that, for every edge Ek , there are two different vertices vs ,vt ∈Ek satisfying [varphi](vs )...0;[varphi](vt ) .
If the color problem is solvable, then each vertex in V has been colored by one of the colors. Thus, for given q colors, we can define a CLV xt =δqs ∈Δq corresponding to the vertex vt ∈V with the color cs ; that is, [varphi](vt )=cs . Before investigating the coloring problem of H , we first calculate the structure matrix of the q valued function xs [ecedil]9;xt for xs ,xt ∈Δq .
Similar to (12), the q valued retrievers can be given as [19] [figure omitted; refer to PDF] and then, xs =Ss,qn[x, left closed]i=1nxi and xt =St,qn[x, left closed]i=1nxi . Let Mr,qn =Diag{δqn 1 ,δqn 2 ,...,δqnqn } and Hq =Diag{e1 ,e2 ,...,eq } , where ei =(δqi)T . With simple calculation, we have [figure omitted; refer to PDF]
Define the structure matrix of [ecedil]9; by [figure omitted; refer to PDF] Next, we give the following algebraic condition of coloring problem of hypergraph H .
Theorem 16.
The coloring problem is solvable if and only if there exists j∈{1,2,...,qn } such that [figure omitted; refer to PDF] where [figure omitted; refer to PDF] J2 =[1,1,...,1]q , and MstH , a structure matrix of [ecedil]9; , is HqSs,qn (Iqn [ecedil]7;St,qn )Mr,qn by (31).
Proof.
(Necessity) If the coloring problem is solvable, then, for every edge Ek ∈... , there exist two different vertices vs ,vt in Ek such that [varphi](vs )...0;[varphi](vt ) . That is, aks =akt =1 but xs ...0;xt . Then, for each k∈{1,2,...,m} , there exist s,t∈{1,2,...,n} , s...0;t , satisfying aks =akt =1 but xs ...0;xt , which implies J2xs [ecedil]9;xt =0<1 . Thus, [figure omitted; refer to PDF] By (31), we have [figure omitted; refer to PDF] Equivalently, [figure omitted; refer to PDF] where Y=[x, left closed]i=1nxi . Considering that Y=[x, left closed]i=1nxi ∈Δqn , from the inequality (37), we know that there exists j∈{1,2,...,qn } such that Colj (M)...a;b .
(Sufficiency) Assume that there exists j∈{1,2,...,qn } such that Colj (M)...a;b . Then the inequality (37) has a solution Y∈Δqn . Thus, for every k∈{1,2,...,m} , the inequality (35) holds. Noticing that 0...4;J2xs [ecedil]9;xt ...4;1 , we get that, for each k∈{1,2,...,m} , there exist s,t∈{1,2,...,n},s...0;t such that aks =akt =1 implies J2xs [ecedil]9;xt =0<1 . Hence, the proof is completed.
Based on the algebraic equivalent condition of the coloring problem, we can construct an algorithm to find out all the coloring schemes and coloring partitions.
Algorithm 17.
Consider the hypergraph H and let a color set N={c1 ,c2 ,...,cq } . Each vertex vt corresponds to a color and, thus, corresponds to a q valued CLV xt ∈Δq . We give the following steps to calculate all the coloring schemes.
(1) Calculate the matrices M and b given in Theorem 16.
(2) Find if there exists j∈{1,2,...,qn } such that Colj (M)...a;b . If not, the coloring problem with the q colors is not solvable, and stop. Otherwise, find out all the columns of M satisfying the inequality (33) and denote their indexes by the set [figure omitted; refer to PDF]
(3) Let [x, left closed]l=1nxl =δqn j , for every j∈Q . By (30), we get xi =Si,qn ([x, left closed]l=1nxl )=Si,qnδqn j , i=1,2,...,n . Then, let [figure omitted; refer to PDF] where Sck j is the set of vertices colored by the k th color, k∈{1,2,...,q} . Then, there are |Q| kinds of coloring schemes corresponding to the elements in Q .
With the result of Theorem 16, we can easily obtain a corollary on Sck j ,k∈{1,2,...,q} , j∈Q .
Corollary 18.
Assume that there exists j∈{1,2,...,qn } such that Colj (M)...a;b . Then, the following hold:
(1) for each k∈{1,2,...,q} , Sck j defined in Algorithm 17 is a stable set of H ,
(2) for each j∈Q , {Sc1 j ,Sc2 j ,...,Scq j } is a partition of the vertices of H .
Remark 19.
From Theorem 16 and Corollary 18, we know that if the coloring problem is solvable with the given q colors, the hypergraph is q -colorable. On the other hand, given the q colors, the coloring schemes obtained in Algorithm 17 contain all the coloring schemes with the colors not more than q . Then, the chromatic number denoted by χ(H) , which is the minimum number of colors being used, is χ(H)=minj∈Q {|Nj |} , where Nj ={i|"Sci j ...0;...,1...4;i...4;q} . Therefore, the minimum coloring partition is [figure omitted; refer to PDF]
5. Application in Storing Problem
A company produces n kinds of chemicals which contain some products that cannot be put in the same storehouse. The problem is that how many storehouses are needed at least to store the n kinds of chemicals and how to assign them. In order to solve the problem, we denote the n kinds of chemicals by V={v1 ,v2 ,...,vn } and m kinds of circumstances by ...={E1 ,E2 ,...,Em } where the chemicals in Ei ⊆V , i=1,2,...,m , cannot be put in the same storehouse. Immediately, we obtain a hypergraph H=(V,...) . Then some chemicals can be put in the same storehouse if and only if the vertices corresponding to the chemicals can be colored with the same color. Therefore, to assign these chemicals is equivalent to solve the coloring problem of H . Here, we will give the following numerical example to illustrate it.
Example 20.
There are five kinds of chemicals denoted by V={v1 ,v2 ,v3 ,v4 ,v5 } needed to be put into two storehouses. Let a hypergraph H have the vertex set as V . And we know that some dangerous thing will happen if the following combinations appear: {v1 ,v2 ,v3 } , {v3 ,v4 ,v5 } , {v2 ,v3 ,v4 } , and {v2 ,v4 ,v5 } . Then we consider that these combinations are edges of the hypergraph. Thus, the storing problem is equivalent to the hypergraph coloring problem with two different colors. Letting a two-color set N={c1 =Red,c2 =Blue} , by Algorithm 17, we can get all the coloring schemes.
The incidence matrix of the hypergraph H is as follows: [figure omitted; refer to PDF] By Theorem 16, using MATLAB toolbox, we easily obtain [figure omitted; refer to PDF] Then, the index set Q of j satisfying (33) is [figure omitted; refer to PDF]
For each j∈Q , let [x, left closed]i=15xi =δ25 j . By computing xi =Si,25δ25 j ,i=1,2,...,5 , we have [figure omitted; refer to PDF] from which we obtain the following 12 coloring schemes: [figure omitted; refer to PDF] Thus, there are totally 12 kinds of storing methods.
6. Conclusion
In this paper, the stable set and vertex coloring problems of hypergraphs have been revised. Several new results and algorithms have been presented via a method of STP. By defining the incidence matrix of hypergraph and CLV of a vertex subset, one equivalent condition has been established for hypergraph stable set. And a new algorithm to find out all the stable sets and all the absolutely maximum stable sets has been obtained. Furthermore, we have considered the vertex coloring problem and got a necessary and sufficient condition in the form of algebraic inequality, by which an algorithm has been derived to search all the coloring schemes and minimum coloring partitions with the given q colors for any hypergraph. Finally, the illustrative example and the application to storing problem have shown that the results presented in this paper are very effective. In papers [34, 35], the scheduling jobs can induce a mixed graph coloring, not a hypergraph coloring. Thus, the mixed graph coloring problem will be interesting to be discussed by STP in the future.
Acknowledgments
The work was partially supported by NNSF of China (61374025), Research Awards Young and Middle-Aged Scientists of Shandong Province (BS2011SF009, BS2011DX019), Excellent Youth Foundation of Shandongs Natural Scientific Committee (JQ201219).
Conflict of Interests
The authors declare that there is no conflict of interests regarding the publication of this paper.
[1] D. Traskov, M. Heindlmaie, M. Médard, R. Koetter, D. S. Lun, "Scheduling for network coded multicast: a conflict graph formulation," in Proceedings of the IEEE GLOBECOM Workshops, pp. 1-5, New Orleans, La, USA, December 2008.
[2] M. Yang, Y. Yang, "A hypergraph approach to linear network coding in multicast networks," IEEE Transactions on Parallel and Distributed Systems , vol. 21, no. 7, pp. 968-982, 2010.
[3] N. Barnier, P. Brisset, "Graph coloring for air traffic flow management," Annals of Operations Research , vol. 130, no. 1-4, pp. 163-178, 2004.
[4] M. W. Carter, G. Laporte, S. Y. Lee, "Examination timetabling: algorithmic strategies and applications," Journal of the Operational Research Society , vol. 47, no. 3, pp. 373-383, 1996.
[5] G. J. Chaitin, M. A. Auslander, A. K. Chandra, J. Cocke, M. E. Hopkins, P. W. Markstein, "Register allocation via coloring," Computer Languages , vol. 6, no. 1, pp. 47-57, 1981.
[6] A. Gamst, "Some lower bounds for a class of frequency assignment problems," IEEE Transactions on Vehicular Technology , vol. 35, no. 1, pp. 8-14, 1986.
[7] B. Wang, J.-L. Wu, "Total colorings of planar graphs without intersecting 5-cycles," Discrete Applied Mathematics , vol. 160, no. 12, pp. 1815-1821, 2012.
[8] B. Wang, J.-L. Wu, "Total colorings of planar graphs with maximum degree seven and without intersecting 3-cycles," Discrete Mathematics , vol. 311, no. 18-19, pp. 2025-2030, 2011.
[9] X. Zhang, J.-L. Wu, "On edge colorings of 1-planar graphs," Information Processing Letters , vol. 111, no. 3, pp. 124-128, 2011.
[10] H. Shen, S. Lv, X. Dong, J. Deng, X. Wang, X. Zhou, "Hypergraph modeling and approximation algorithms for the minimum length link scheduling in multiuser MIMO networks," Journal of Applied Mathematics , vol. 2013, 2013.
[11] F. M. Malvestuto, "Decomposable convexities in graphs and hypergraphs," ISRN Combinatorics , vol. 2013, 2013.
[12] L. R. Nielsen, A. R. Kristensen, "Finding the K best policies in a finite-horizon Markov decision process," European Journal of Operational Research , vol. 175, no. 2, pp. 1164-1179, 2006.
[13] J. Freixas, M. A. Puente, "Dimension of complete simple games with minimum," European Journal of Operational Research , vol. 188, no. 2, pp. 555-568, 2008.
[14] C. Bentz, D. Cornaz, B. Ries, "Packing and covering with linear programming: a survey," European Journal of Operational Research , vol. 227, no. 3, pp. 409-422, 2013.
[15] A. Jiménez-Losada, J. R. Fernández, M. Ordóñez, M. Grabisch, "Games on fuzzy communication structures with Choquet players," European Journal of Operational Research , vol. 207, no. 2, pp. 836-847, 2010.
[16] V. Voloshin, H.-J. Voss, "Circular mixed hypergraphs II: the upper chromatic number," Discrete Applied Mathematics , vol. 154, no. 8, pp. 1157-1172, 2006.
[17] J. Li, L. Wang, H. Zhao, "On packing and coloring hyperedges in a cycle," Discrete Applied Mathematics , vol. 155, no. 16, pp. 2140-2151, 2007.
[18] P. D. Johnson Jr., R. N. Mohapatra, "A class of inequalities relating degrees of adjacent nodes to the average degree in edge-weighted uniform hypergraphs," International Journal of Mathematics and Mathematical Sciences , vol. 2005, no. 21, pp. 3419-3426, 2005.
[19] D. Cheng, H. Qi Semi-Tensor Product of Matrices: Theory and Applications , Science Press, Beijing, China, 2007.
[20] D. Cheng, H. Qi, Z. Li Analysis and Control of Boolean Networks: A Semi-Tensor Product Approach , of Communications and Control Engineering Series, pp. xvi+470, Springer, London, UK, 2011.
[21] D. Cheng, H. Qi, "Controllability and observability of Boolean control networks," Automatica , vol. 45, no. 7, pp. 1659-1667, 2009.
[22] D. Cheng, H. Qi, "A linear representation of dynamics of Boolean networks," IEEE Transactions on Automatic Control , vol. 55, no. 10, pp. 2251-2258, 2010.
[23] D. Cheng, Z. Li, H. Qi, "Realization of Boolean control networks," Automatica , vol. 46, no. 1, pp. 62-69, 2010.
[24] D. Cheng, "Disturbance decoupling of boolean control networks," IEEE Transactions on Automatic Control , vol. 56, no. 1, pp. 2-10, 2011.
[25] D. Cheng, H. Qi, Z. Li, J. B. Liu, "Stability and stabilization of Boolean networks," International Journal of Robust and Nonlinear Control , vol. 21, no. 2, pp. 134-156, 2011.
[26] D. Laschov, M. Margaliot, "A maximum principle for single-input Boolean control networks," IEEE Transactions on Automatic Control , vol. 56, no. 4, pp. 913-917, 2011.
[27] F. Li, J. Sun, "Controllability of Boolean control networks with time delays in states," Automatica , vol. 47, no. 3, pp. 603-607, 2011.
[28] H. Li, Y. Wang, "Boolean derivative calculation with application to fault detection of combinational circuits via the semi-tensor product method," Automatica , vol. 48, no. 4, pp. 688-693, 2012.
[29] Z. Liu, Y. Wang, "Disturbance decoupling of mix-valued logical networks via the semi-tensor product method," Automatica , vol. 48, no. 8, pp. 1839-1844, 2012.
[30] J. Feng, J. Yao, P. Cui, "Singular Boolean networks: semi-tensor product approach," Science China Information Sciences , vol. 56, no. 11, pp. 1-14, 2013.
[31] Y. Wang, C. Zhang, Z. Liu, "A matrix approach to graph maximum stable set and coloring problems with application to multi-agent systems," Automatica , vol. 48, no. 7, pp. 1227-1236, 2012.
[32] R. A. Horn, C. R. Johnson Topics in Matrix Analysis , pp. viii+607, Cambridge University Press, Cambridge, Mass, USA, 1991.
[33] C. Berge Graphs and Hypergraphs , pp. xiv+528, North-Holland, Amsterdam, The Netherlands, 1973.
[34] Y. N. Sotskov, V. S. Tanaev, F. Werner, "Scheduling problems and mixed graph colorings," Optimization , vol. 51, no. 3, pp. 597-624, 2002.
[35] F. S. Al-Anzi, Y. N. Sotskov, A. Allahverdi, G. V. Andreev, "Using mixed graph coloring to minimize total completion time in job shop scheduling," Applied Mathematics and Computation , vol. 182, no. 2, pp. 1137-1148, 2006.
You have requested "on-the-fly" machine translation of selected content from our databases. This functionality is provided solely for your convenience and is in no way intended to replace human translation. Show full disclaimer
Neither ProQuest nor its licensors make any representations or warranties with respect to the translations. The translations are automatically generated "AS IS" and "AS AVAILABLE" and are not retained in our systems. PROQUEST AND ITS LICENSORS SPECIFICALLY DISCLAIM ANY AND ALL EXPRESS OR IMPLIED WARRANTIES, INCLUDING WITHOUT LIMITATION, ANY WARRANTIES FOR AVAILABILITY, ACCURACY, TIMELINESS, COMPLETENESS, NON-INFRINGMENT, MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Your use of the translations is subject to all use restrictions contained in your Electronic Products License Agreement and by using the translation functionality you agree to forgo any and all claims against ProQuest or its licensors for your use of the translation functionality and any output derived there from. Hide full disclaimer
Copyright © 2014 Min Meng and Jun-e Feng. Min Meng et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Abstract
This paper considers the stable set and coloring problems of hypergraphs and presents several new results and algorithms using the semitensor product of matrices. By the definitions of an incidence matrix of a hypergraph and characteristic logical vector of a vertex subset, an equivalent algebraic condition is established for hypergraph stable sets, as well as a new algorithm, which can be used to search all the stable sets of any hypergraph. Then, the vertex coloring problem is investigated, and a necessary and sufficient condition in the form of algebraic inequalities is derived. Furthermore, with an algorithm, all the coloring schemes and minimum coloring partitions with the given q colors can be calculated for any hypergraph. Finally, one illustrative example and its application to storing problem are provided to show the effectiveness and applicability of the theoretical results.
You have requested "on-the-fly" machine translation of selected content from our databases. This functionality is provided solely for your convenience and is in no way intended to replace human translation. Show full disclaimer
Neither ProQuest nor its licensors make any representations or warranties with respect to the translations. The translations are automatically generated "AS IS" and "AS AVAILABLE" and are not retained in our systems. PROQUEST AND ITS LICENSORS SPECIFICALLY DISCLAIM ANY AND ALL EXPRESS OR IMPLIED WARRANTIES, INCLUDING WITHOUT LIMITATION, ANY WARRANTIES FOR AVAILABILITY, ACCURACY, TIMELINESS, COMPLETENESS, NON-INFRINGMENT, MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Your use of the translations is subject to all use restrictions contained in your Electronic Products License Agreement and by using the translation functionality you agree to forgo any and all claims against ProQuest or its licensors for your use of the translation functionality and any output derived there from. Hide full disclaimer