Robust graph coloring based on the matrix semi-tensor product with application to examination timetabling

Meirong XU,Yuzhen WANG,Airong WEI

1.School of Control Science and Engineering,Shandong University,Jinan Shandong 250061,China;

2.School of Mathematical Sciences,University of Jinan,Jinan Shandong 250022,China

Robust graph coloring based on the matrix semi-tensor product with application to examination timetabling

Meirong XU1,2?,Yuzhen WANG1,Airong WEI1

1.School of Control Science and Engineering,Shandong University,Jinan Shandong 250061,China;

2.School of Mathematical Sciences,University of Jinan,Jinan Shandong 250022,China

This paper investigates the robust graph coloring problem with application to a kind of examination timetabling by using the matrix semi-tensor product,and presents a number of new results and algorithms.First,using the matrix semi-tensor product,the robust graph coloring is expressed into a kind of optimization problem taking in an algebraic form of matrices,based on which an algorithm is designed to find all the most robust coloring schemes for any simple graph.Second,an equivalent problem of robust graph coloring is studied,and a necessary and sufficient condition is proposed,from which a new algorithm to find all the most robust coloring schemes is established.Third,a kind of examination timetabling is discussed by using the obtained results,and a method to design a practicable timetabling scheme is presented.Finally,the effectiveness of the results/algorithms presented in this paper is shown by two illustrative examples.

Robust graph coloring;Algorithm;Examination timetabling;Semi-tensor product

1 Introduction

The coloring problem,a classical problem of graph theory,was shown a very difficult and NP-hard problem in the earlier 70's of the last century.It has not only played an important role in the development of graph theory,but also found a wide range of applications in real life such as air traffic flow management[1],timetabling[2,3],scheduling[4],and frequency assignment[5].The problem shows up in an incredible variety of forms such as vertex coloring,edge coloring,bandwidth coloring,list coloring,set coloring,T-coloring,λ-coloring,circular coloring.Among them,the vertex coloring problem is a well-known one,in which each vertex of a graph is assigned one color such that no adjacent vertices share the same color.Usually,the vertex coloring problem can be considered either as ak-colorable problem or as the so-called minimum coloring problem.

As an extension of the classical vertex coloring problem,the robust graph coloring problem(RGCP)was first put forward by Y'a?nez and Ram'?rez[6].Generally speaking,the RGCP focuses on studying the possibility of adding edges for a given graph with a beforehand designed coloring scheme under the condition that no more number of colors is needed.This problem can be described as follows:given a vertex coloring scheme for a graph,and assigning a penalty for each pair of nonadjacent vertices which share the same color,the objective of the RGCP is to minimize the sum of penalties.Up to now,the RGCP has found many applications in course scheduling,cluster analysis,map coloring and crew assignment,etc.[6,7].Moreover,several works have devoted to study the RGCP,and some useful algorithms,such as genetic algorithm[6],metaheuristics(based on various encoding schemes and neighborhood structures)[7]and exact algorithm[8],were put forwarded.

It is noted that a new powerful mathematical tool called the semi-tensor product of matrices was proposed by Cheng[9,10],which has been successfully applied to express and analyze Boolean control network up to now[11-17].It is also noticed that this new tool was used in[18]to investigate the vertex coloring problem,and some necessary and sufficient conditions were presented for thek-coloring problem.According to the method of[18],one can easily determine all thekcoloring schemes for a given graph only through computing a kind of structural matrix.For other successful applications of the semi-tensor product,please see[19-25].

In this paper,we investigate the RGCP by using the semi-tensor product of matrices,and present some new results and algorithms to solve the RGCP.First,using the matrix semi-tensor product,the robust graph coloring is expressed into a kind of optimization problem taking in an algebraic form of matrices,based on which an algorithm is designed to find all the most robust coloring schemes for any simple graph.Second,an equivalent problem of robust graph coloring is studied,and a necessary and sufficient condition is proposed,from which a new algorithm to find all the most robust coloring schemes is established.Third,a kind of examination timetabling is discussed by using the obtained results,and a method to design a practicable timetabling scheme is presented.Finally,we give two illustrative examples to show the effectiveness of the results/algorithms presented in this paper.

The main contributions of this paper are as follows.i)The semi-tensor product method is first used to investigate the RGCP,and a new mathematical formulation has been established.ii)A set of new theoretical results(necessary and sufficient conditions)and algorithms are obtained to deal with the RGCP.iii)A new method to design a practicable timetabling scheme is presented for a kind of examination timetabling.It is well worth pointing out that the main advantage of our approach lies in expressing the robust graph coloring problem in an algebraic form of matrices,which is such a clear way that it may be very helpful for further study of the problem.Moreover,we can easily to find all the most robust coloring schemes by our method for a given graph with a small size of vertices.However,it should be noted that our method does not reduce the computational complexity,since the problem is proved to be NP-hard[6],and it is impossible to design an exact algorithm to solve this problem in polynomial time for a general graph.

The remainder of the paper is organized as follows.Section 2 is some preliminaries on the semi-tensor product and graph theory.In Section 3,we investigate the RGCP and present the main results of this paper.Section 4 deals with the examination timetabling problem.Two illustrative examples are given in Section 5 to support our new results/algorithms,which is followed by the conclusion in Section 6.

2 Preliminaries

In this section,we give some necessary preliminaries on the semi-tensor product and graph theory,which will be used in the sequel.First,we briefly recall the basic concepts and properties of the semi-tensor product.

Definition 1[9] 1)LetXbe a row vector of dimensionnp,andYbe a column vector with dimensionp.Then,we splitXintopequal-size blocks asX1,...,XP,which are 1Xnrows.Define the(left)semi-tensor product,denoted by■,as

whereyi∈R is theith component ofY.

2)LetA∈RmXnandB∈RpXq.If eithernis a factor ofp,say,nt=pand denote it asA?tB,orpis a factor ofn,say,n=ptand denote it asA?tB,then we define the(left)semi-tensor product ofAandB,denoted byas follows:Cconsists ofmXqblocks asC=(Cij)and each block is

whereAiis theith row ofAandBjis thejth column ofB.

It is noted that the semi-tensor product is a generalization of the conventional matrix product,and thus the symbol'■'can be omitted in most cases.

Remark 1From Definitions 1,it is easy to see that[9]

The following notations will be used later:

Thek-valued power-reducing matrix is given as[9]

AnnXtmatrixLis called a logical matrix ifL=and for compactness,we expressLbriefly as

The set ofnXtlogical matrices is denoted byLet Coli(A)denote theith column of a matrixA,and the set of all the columns ofAis denoted by Col(A).

Lemma 1[10] Anyn-aryk-valued logical functionwith logical variablesxi∈Δk,i=1,2,...,n,can be expressed as

whereMf∈LkXknis unique,called the structure matrix off,and

Next,we recall some basic concepts and properties of graph theory.

A graph G consists of a vertex(node)set V={v1,v2,...,vn}and an edge set ??VXV,denoted by G={V,?}.A graph G={V,?}is called to be simple,if each edgee∈? is described by a pair of two distinct vertices.The complement graph of agraph G={V,?}is the graphwhere

For a vertexvi,the neighborhood ofvi,Ni,is defined as

The adjacency matrix,A=[aij],of G is given by

The coloring problemGiven a graph G={V,?}with V={v1,v2,...,vn},let φ :be a mapping,wherec1,...,ckstand forkkinds of different colors.The coloring problem is to find a suitable coloring mapping φ such that for anyvi,vj∈ V,if(vi,vj)∈ ?,then φ(vi)≠ φ(vj).

For each vertexvi∈V,assign it ak-valued characteristic logical variablexi∈Δkas follows[18]:

Then,the following results were obtained in[18].

Lemma 2[18]Consider a graph G={V,?},and let a coloring mapping φ :be given.Then,the coloring problem is solvable with the given φ,if and only if the followingn-aryk-valued pseudo-logic equation

is solvable,where 0kis thek-dimensional zero vector,and⊙is the Hadamard product of matrices/vectors.

Lemma 3[18]Consider a graph G={V,?},and let a color setN={c1,...,ck}be given.Then,the coloring problem of G is solvable with a mapping φ :,if and only if

3 Main results

In this section,we investigate the robustk-coloring problem by the semi-tensor product method,and present the main results of this paper.

The RGCP is to find a suitablek-coloring mapping φ such that thek-coloring problem is solvable with φ and meantime,R(φ)is minimized,that is,

Remark 21)If the complementary edgewhose endpoints sharing the same color is added to the graph G,then the given coloring mapping φ will be invalid.In this case,pij>0 will play the role of signing the invalidness of(vi,vj)∈ˉ?,that is,the complementary edge(vi,vj)cannot be added for the given coloring mapping.

2)We can assign different penalty for each complementary edge according to different application and physical meaning in practice(see Section 4 below).

3)The rigidity level is a measurement of coloring robustness of a given coloring mapping φ.Obviously,the lower level represents the more robustness of the coloring.

In order to investigate the RGCP,we define a new pseudo-logic function first.

Definition 2Ann-aryk-valued pseudo-logic functiong(x1,x2,...,xn)is a mapping fromto R,whereandxi∈ Δk,i=1,2,...,n.

For each vertexvi∈V,we assign it ak-valued characteristic logical variablexi∈ Δkas follows:

Letand define

Then,the rigidity level of the coloring mapping φ can be expressed as

which is ann-aryk-valued pseudo-logic function.

Moreover,by Lemma 2 and the above analysis,it is easy to see that the robust coloring problem is equivalent to the following constrained optimization problem:

Remark 31)If allpij=1,then the RGCP is to find a suitable coloring mapping φ such that the number of complementary edges whose vertices share the same color is minimum.Or equivalently,to find a suitable coloring mapping φ such that the number of possible complementary edges is maximum,where a possible complementary edge is one that if it is added to the original graph,the coloring mapping φ is still valid.

2)If allpij=c>0,wherecis a constant,the RGCP is the same as that in the case of allpij=1.Other case is different.

Based on Remark 3,our study is divided into the following two cases:

Case IThe RGCP with allpij=1.

In this case,using the semi-tensor product,we express the rigidity level of a given coloring into a matrix algebraic form via the structural matrix first,which leads to the following result.

Proposition 1For the rigidity level(11),there exists a unique matrixsuch that

where

and

are given as[9].

ProofWith(13),we have

Based on this,we obtain

In fact,if there exists anothersuch that

Remark 4is the structural matrix of the pseudological functionR(x1,x2,...,xn),and the minimum component ofis the global minimum of the rigidity levelR(x1,x2,...,xn).

According to Proposition 1 and Lemma 3,the RGCP can be expressed in an algebraic form of matrices as

With above analysis,we can establish the following algorithm to obtain all the most robust coloring schemes for any simple graph.

Algorithm 1Given a simple graph G withnverticeslet a color setbe given.For each vertexvi,we assign it ak-valued characteristic logical variablexi∈ Δk.We can obtain all the most robust coloring schemes of G by taking the following steps:

S1)Compute the matrixMand the row vectorgiven in(15).

S2)Check whether 0k∈Col(M)or not.If 0k?Col(M),the coloring problem with the given color set has no solution,which implies that the RGCP is not solvable,and the algorithm is ended.Otherwise,label the columns which equal 0kand set

S3)Calculateand the corresponding column index

and the corresponding most robust coloring scheme is given as

Next,we present a theorem,which provides us with another more practical method to solve the RGCP.

Theorem 1A pointis a global solution to the following optimization problem:

such thatwhereis ann-aryk-valued pseudo-logic function and ν=

ProofObviously,

Thus,

On the other hand,noticing thatsatisfies(17),we have

Hence,

which is a contradiction with(18).Therefore,satisfies(17).

From above,it is easy to know that

Thus,inequality(18)can be expressed as

which is in contradiction with

Hence,

Moreover,it is easy to see from(19)that

In fact,if not,similarly,we have

This is a contradiction.Hence,satisfies(17),and

Thus,the proof is completed.

According to Theorem 1,we have the following result to solve the RGCP.

Theorem 2Consider a simple graph G={V,?}withnvertices V={v1,v2,...,vn},and let a coloring mapping φ :,withVφ=be given.Setwherecan be uniquely determined.Then,the coloring with the given φ is a most robust coloring if and only if

where

ProofAccording to Theorem 1 and the above analysis of the RGCP,the RGCP is equivalent to find a minimum pointof the following function:

such that

On the other hand,by Lemma 3 and Proposition 1,we have

Hence,if the coloring with the given φ is a most robust coloring,then thesth component of the row vectorM? is the minimum among all the components,which are less than ν.That is,

On the contrary,ifthen thesth component of the row vectoris the minimum among all the components,which are less than ν.Hence,which contents,is the minimum point ofF(x1,x2,...,xn)such thatF(x1,x2,...,xn) ≤ ν.According to Theorem 1,(x1,x2,...,xn)is a global optimal solution to the constrained optimization problem(16)and(17),which implies that(x1,x2,...,xn)is a most robust coloring scheme.

Based on the proof of Theorem 2,we present an algorithm to find all the most robust coloring schemes for any simple graph.

Algorithm 2Given a simple graph G withnvertices V={v1,v2,...,vn},let a color set N={c1,c2,...,ck}be given.For each vertexvi,we assign it ak-valued characteristic logical variablexi∈ Δk.To find all the most robust coloring schemes of G,we can do it by taking the following steps:

S2)Calculateand set

Case IIThe RGCP with differentpij.

By a similar argument to Case I,we have the following result on determining whether a coloring is a most robust coloring or not.

Theorem 3Consider a simple graph G={V,?}withnvertices V={v1,v2,...,vn},and its complementary graph is given byLet a penalty setP={pij}and a coloring mapping φ :with,be given.Set wherecan be uniquely determined.Then,the coloring mapping φ is a most robust coloring if and only if

where

andMijandMare the same as those in Proposition 1 and(15).

ProofThe proof is similar to that of Theorem 2,and thus it is omitted.

Remark 5Theorem 3 can also provide us with an effective algorithm to find all the most robust coloring schemes for any simple graph,which is similar to Algorithm 3 and thus omitted.

4 Application to examination timetabling

Examination timetabling is a significant administrative issue that arises in academic institutions.In an examination timetabling problem,a number of examinations are allocated into a given number of time slots subject to constrains,which are usually divided into two inde-pendent categories:hard and soft constraints[3,26].Hard constraints need to be satisfied under any circumstances,while soft constraints are those being desirable to satisfy,but they are not essential.For a real-world university timetabling problem,it is usually impossible to satisfy all the soft constraints.Based on this,an examination timetabling is to find a feasible timetable,which satisfies all of the hard constraints,such that the violation of the soft constraints is minimal.

In this section,as an application,we use the results obtained in Section 3 to investigate a kind of examination timetabling problem.

Consider an examination timetabling ofnexams withkavailable time slots.Assume that there are the socalled 'standard students' and 'non-standard students'.Standard students are these who are studying according to basic studies plans and non-standard ones are those who repeated courses.Besides,the hard constraints and soft ones,considered in this paper,are listed as follows.

The hard constraints are

1)All exams must be scheduled,and each exam must be scheduled only once.

2)No standard student can take two exams concurrently.

The soft constraints are

1)No non-standard student can take two exams concurrently.

2)The exams should be arranged as evenly as possible for all time slots.

Taking account of the hard constraints,we can obtain a feasible examination timetable by solving thekcoloring of graph G={V,?},where V={v1,v2,...,vn}represents the set of the exam courses and the edge(vi,vj)∈? exists when the examination coursesviandvjshare at least one standard student.

Next,we consider the violation of the soft constraints for the feasible timetable.

For each examination coursevi∈V,we assign it akvalued characteristic logical variablexi∈ Δkas follows:

Assume thatis a conflict matrix,wheredijis the proportion of non-standard students taking both examsviandvj,i,j=1,2,...,n.Then,the violation of the soft constraint(1)can be quantified as

Remark 6Ifaij=1,the value ofdijdoes not affect the violation of the soft constraint(1).In this case,for the simplicity,we denotedij=0,and similarlydii=0.

In the same way,the violation degree of the soft constraint(2)is formulated as

which implies that the violation of the soft constraint(2)will be decreased as the the number of exams arranged on the same time slot tends to uniform for all the time slots.

Taking account of both the soft constraints,and assuming each one with a weightwk,k=1,2,the violation of the soft constraints for the feasible timetable can be defined as follows:

Thus,the examination timetabling problem is to find a suitable timetable for the following optimization problem:

Applying the results of Theorem 3,we have the following result on the examination timetabling problem.

Proposition 2Considernexaminations,...,vn}with its topology of graph G={V,?}for the standard students courses incompatibilities,and letkavailable time slots N={c1,...,ck},a penalty setP={ˉpij}for the soft constraint(1)and an examination timetable mappingφ :with,be given.Setwhere 1≤s≤kncan be uniquely determined.Then,φ is a most feasible timetable mapping for the soft constraints(1)and(2)if and only if

where

w1andw2are the weight of the soft constraints(1)and(2),respectively,andandare the same as those in Proposition 1 and(15).

5 Illustrative examples

In this section,we give two examples to illustrate the effectiveness of the results obtained in this paper.

Example 1Consider the graph G={V,?}shown in Fig.1.Letting a two-color setN={C1=red,C2=blue}be given,we use Algorithm 3 to find out all the most robust coloring schemes for G.

Fig.1 An undirected graph.

For each vertexvi,we assign it a characteristic logical variablexi∈ Δ,i=1,2,3,4.The adjacency matrix of this graph is as follows:

By(3)and the MATLAB toolbox which is provided by D.Cheng and his co-workers,we can easily obtain

It is observed that

and the corresponding column index set is

Calculate

and the corresponding column indexj?=7,10.

Thus,all the most robust coloring schemes are as follows:

and

Example 2Consider an examination timetabling of 4 exams with 2 available time slots.Assume that the information topology of the examinations for the standard students is given by a graph G={V,?}with V={v1,v2,v3,v4}shown in Fig.1,wherev1,v2,v3,v4stand for the 4 different examinations.Moreover,let the matrixwheredijis the proportion of nonstandard students taking both the examinationsviandvj,be given as

In this example,we assume that the weight of the soft constraints(1)and(2)in Proposition 2 isw1=1 andw2=0.Then,we apply Proposition 2 to find all the most feasible examination timetables to ensure that no standard student takes two examinations concurrently and make the examinations sharing more non-standard students be scheduled at different time slots as much as possible.

For each examvi,we assign it a 2-valued characteristic logical variablexi∈ Δ2,i=1,2,3,4.

To ensure a feasible timetable which make the examinations sharing more non-standard students be scheduled the different time slot has a lower violation than another one with the same time slot,we let the penalty for the examinationsviandvjbe defined aspij=4100s,ifwhere 4 denotes the number of the complement edges for the graph G.

Using Proposition 2,we obtain

It is easy to know that

and the corresponding column indexs=8,9.

By computingwe have

Thus,we can obtain all the most feasible time schemes as

and

6 Conclusions

In this paper,the robust graph coloring problem with application to a kind of examination timetabling problem is studied,and a number of new results and algorithms are presented.Using the semi-tensor product,the robust graph coloring problem is expressed into a kind of optimization problem taking in an algebraic form of matrices,and an algorithm is designed to find all the most robust coloring schemes for any simple graph.Furthermore,an equivalent problem of the robust graph coloring is studied,and a necessary and sufficient condition is proposed,from which a new algorithm to find all the most robust coloring schemes is established.In addition,as an application,a kind of examination timetabling is discussed by employing aforementioned results,and a method to design a practicable timetabling scheme is achieved.The study of two illustrative examples has shown the effectiveness of these results/algorithms presented in this paper.

[1]N.Barnier,P.Brisset.Graph coloring for air traffic flow management.Annals of Operations Research,2004,130(1/4):163-178.

[2]E.Burke,D.Elliman,R.Weare.A university timetabling system based on graph colouring and constraint manipulation.Journal of Research on Computing in Education,1994,27(1):1-18.

[3]M.Carter,G.Laporte,S.Lee.Examination timetabling:algorithmic strategies and applications.Journal of the Operational Resaerch Society,1996,47(3):373-383.

[4]K.Giaro,M.Kubale,P.Obszarski.A graph coloring approach to scheduling of multiprocessor tasks on dedicated machines with availability constraints.Discrete Applied Mathematics,2009,157(17):3625-3630.

[5]A.Gamst.Some lower bounds for a class of frequency assignment problems.IEEE Transactions on Vehicular Technology,1986,35(1):8-14.

[6]J.Y'a?nez,J.Ram'?rez.The robust coloring problem.European J.of Operational Research,2003,148(3):546-558.

[7]F.Wang,Z.Xu.Meta-heuristics for robust graph coloring.Journal of Heuristics,2013,19(4):529-548.

[8]R.Bracho,J.Rodriguez,F.Martinez.Algorithms for robust graph coloring on paths.Proceedings of the 2nd International Conference on Electrical and Electronics Engineering.New York:IEEE,2005:9-12.

[9]D.Cheng,H.Qi.Semi-tensor product of matrices theory and applications.Beijing:Science Press,2007(in Chinese).

[10]D.Cheng,H.Qi,Z.Li.Analysis and Control of Boolean Networks:A Semi-tensor Product Approach.Berlin:Springer,2011.

[11]D.Cheng,H.Qi.A linear representation of dynamics of Boolean networks.IEEE Transactions on Automatic Control,2010,55(10):2251-2258.

[12]D.Cheng,H.Qi.Controllability and observability of Boolean control networks.Automatica,2009,45(7):1659-1667.

[13]D.Cheng,Z.Li,H.Qi.Realization of Boolean control networks.Automatica,2010,46(1):62-69.

[14]D.Cheng.Disturbance decoupling of Boolean control networks.IEEE Transactions on Automatic Control,2011,56(1):2-10.

[15]D.Cheng,H.Qi,Z.Li,et al.Stability and stabilization of Boolean networks.International Journal of Robust and Nonlinear Control,2011,21(2):134-156.

[16]D.Cheng,Y.Zhao,X.Xu.From Boolean algebra to Boolean calculus.Control Theory&Applications,2011,28(10):1513-1523.

[17]H.Qi,D.Cheng.Logic and logic-based control.Journal of Control Theory and Applications,2008,6(1):26-36.

[18]Y.Wang,C.Zhang,Z.Liu.A matrix approach to graph maximum stable set and coloring problems with application to multi-agent systems.Automatica,2012,48(7):1227-1236.

[19]D.Laschov,M.Margaliot.A maximum principle for singleinput Boolean control networks.IEEE Transactions on Automatic Control,2011,56(4):913-917.

[20]F.Li,J.Sun.Controllability of higher order Boolean control networks.Applied Mathematics and Computation,2012,219(1):158-169.

[21]Z.Li,D.Cheng.Algebraic approach to dynamics of multi-valued networks.International Journal of Bifurcation and Chaos,2010,20(3):561-582.

[22]Z.Liu,Y.Wang.General Logical expression ofk-valued and mixvalued pseudo-logical functions.Proceedings of the 31st Chinese Control Conference.Piscataway:IEEE,2012:66-71.

[23]A.Ge,Y.Wang,A.Wei,et al.Control design for multi-variable fuzzy systems with application to parallel hybrid electric vehicles.Control Theory&Applications,2013,30(8):998-1004.

[24]X.Xu,Y.Hong.Matrix expression and reachability analysis of finite automata.Journal of Control Theory and Applications,2012,10(2):210-215.

[25]Z.Li,J.Song.Controllability and observability of Boolean control networks.Control Theory&Applications,2013,30(6):760-764.

[26]M.Carter.A survey of practical applications of examination timetabling.Operations Research,1986,34(2):193-202.

21 September 2013;revised 10 February 2014;accepted 21 February 2014

DOI10.1007/s11768-014-0153-7

?Corresponding author.

E-mail:ss_xumr@ujn.edu.cn.Tel.:+86-15553178008.

This work was supported by the National Natural Science Foundation of China(Nos.G61374065,G61034007,G61374002),the Fund for the Taishan Scholar Project of Shandong Province,the Natural Science Foundation of Shandong Province(No.ZR2010FM013),and the Scientific Research and Development Project of Shandong Provincial Education Department(No.J11LA01).

?2014 South China University of Technology,Academy of Mathematics and Systems Science,CAS,and Springer-Verlag Berlin Heidelberg

Meirong XUreceived her B.S.degree from Shandong University in 1996,and M.S.degree from Naval Aeronautical Engineering Institute,China,in 2004.Since 2004,she is an associate professor with the School of Mathematical Sciences,University of Jinan,China.She is currently pursuing the Ph.D.degree in the School of Control Science and Engineering,Shandong University,China.Her interests include graph coloring and semi-tensor product.E-mail:ss_xumr@ujn.edu.cn.

Yuzhen WANGgraduated from Tai'an Teachers College in 1986,received his M.S.degree from Shandong University of Science&Technology in 1995 and Ph.D.degree from the Institute of Systems Science,Chinese Academy of Sciences in 2001.From 2001 to 2003,he worked as a postdoctoral fellow in Tsinghua University,Beijing,China.Since 2003,he is a professor with the School of Control Science and Engineering,Shandong University,China,and currently the dean of the School of Control Science and Engineering,Shandong University.From March 2004 to June 2004,from February 2006 to May 2006,and from November 2008 to January 2009,he visited City University of Hong Kong as a research fellow.From September 2004 to May 2005,he worked as a visiting research fellow at the National University of Singapore.His research interests include nonlinear control systems,Hamiltonian systems,Boolean networks,andmulti-agent systems.Prof.Wang received the Prize of Guan Zhaozhi in 2002,the Prize of Huawei from the Chinese Academy of Sciences in 2001,the Prize of Natural Science from Chinese Education Ministry in 2005,and the National Prize of Natural Science of China in 2008.Currently,he is a Taishan Scholar of Shandong Province,China,an associate editor of Asian Journal of Control,and IMA Journal of Math Control and Inform.E-mail:yzwang@sdu.edu.cn.

Airong WEIreceived her M.S.degree from Shandong University of technology in 1997 and Ph.D.degree from School of Control Science and Engineering,Shandong University in 2006.From 2007 to 2009,she worked as a postdoctoral fellow at the School of Mathematics,Shandong University.Currently,she is an associate professor with the School of Control Science and Engineering,Shandong University.Her research interests include nonlinear control systems with constrains,Hamiltonian systems and control of multi-agent systems.E-mail:weiairong@sdu.edu.cn.