A matrix approach to hypergraph stable set and coloring problems with its application to storing problem. (English) Zbl 1463.05184

Summary: 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.


05C15 Coloring of graphs and hypergraphs
05C65 Hypergraphs
Full Text: DOI


[1] Traskov, D.; Heindlmaie, M.; Médard, M.; Koetter, R.; Lun, D. S., Scheduling for network coded multicast: a conflict graph formulation, Proceedings of the IEEE GLOBECOM Workshops
[2] Yang, M.; Yang, Y., A hypergraph approach to linear network coding in multicast networks, IEEE Transactions on Parallel and Distributed Systems, 21, 7, 968-982 (2010)
[3] Barnier, N.; Brisset, P., Graph coloring for air traffic flow management, Annals of Operations Research, 130, 1-4, 163-178 (2004) · Zbl 1062.90011
[4] Carter, M. W.; Laporte, G.; Lee, S. Y., Examination timetabling: algorithmic strategies and applications, Journal of the Operational Research Society, 47, 3, 373-383 (1996)
[5] Chaitin, G. J.; Auslander, M. A.; Chandra, A. K.; Cocke, J.; Hopkins, M. E.; Markstein, P. W., Register allocation via coloring, Computer Languages, 6, 1, 47-57 (1981)
[6] Gamst, A., Some lower bounds for a class of frequency assignment problems, IEEE Transactions on Vehicular Technology, 35, 1, 8-14 (1986)
[7] Wang, B.; Wu, J.-L., Total colorings of planar graphs without intersecting 5-cycles, Discrete Applied Mathematics, 160, 12, 1815-1821 (2012) · Zbl 1245.05053
[8] Wang, B.; Wu, J.-L., Total colorings of planar graphs with maximum degree seven and without intersecting 3-cycles, Discrete Mathematics, 311, 18-19, 2025-2030 (2011) · Zbl 1244.05098
[9] Zhang, X.; Wu, J.-L., On edge colorings of 1-planar graphs, Information Processing Letters, 111, 3, 124-128 (2011) · Zbl 1259.05050
[10] Shen, H.; Lv, S.; Dong, X.; Deng, J.; Wang, X.; Zhou, X., Hypergraph modeling and approximation algorithms for the minimum length link scheduling in multiuser MIMO networks, Journal of Applied Mathematics, 2013 (2013) · Zbl 1397.90193
[11] Malvestuto, F. M., Decomposable convexities in graphs and hypergraphs, ISRN Combinatorics, 2013 (2013) · Zbl 1264.05089
[12] Nielsen, L. R.; Kristensen, A. R., Finding the K best policies in a finite-horizon Markov decision process, European Journal of Operational Research, 175, 2, 1164-1179 (2006) · Zbl 1142.90495
[13] Freixas, J.; Puente, M. A., Dimension of complete simple games with minimum, European Journal of Operational Research, 188, 2, 555-568 (2008) · Zbl 1151.91021
[14] Bentz, C.; Cornaz, D.; Ries, B., Packing and covering with linear programming: a survey, European Journal of Operational Research, 227, 3, 409-422 (2013) · Zbl 1292.90002
[15] Jiménez-Losada, A.; Fernández, J. R.; Ordóñez, M.; Grabisch, M., Games on fuzzy communication structures with Choquet players, European Journal of Operational Research, 207, 2, 836-847 (2010) · Zbl 1205.91041
[16] Voloshin, V.; Voss, H.-J., Circular mixed hypergraphs II: the upper chromatic number, Discrete Applied Mathematics, 154, 8, 1157-1172 (2006) · Zbl 1099.05040
[17] Li, J.; Wang, L.; Zhao, H., On packing and coloring hyperedges in a cycle, Discrete Applied Mathematics, 155, 16, 2140-2151 (2007) · Zbl 1144.90324
[18] Johnson, P. D.; Mohapatra, R. N., 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, 2005, 21, 3419-3426 (2005) · Zbl 1085.05046
[19] Cheng, D.; Qi, H., Semi-Tensor Product of Matrices: Theory and Applications (2007), Beijing, China: Science Press, Beijing, China
[20] Cheng, D.; Qi, H.; Li, Z., Analysis and Control of Boolean Networks: A Semi-Tensor Product Approach. Analysis and Control of Boolean Networks: A Semi-Tensor Product Approach, Communications and Control Engineering Series, xvi+470 (2011), London, UK: Springer, London, UK · Zbl 1209.93001
[21] Cheng, D.; Qi, H., Controllability and observability of Boolean control networks, Automatica, 45, 7, 1659-1667 (2009) · Zbl 1184.93014
[22] Cheng, D.; Qi, H., A linear representation of dynamics of Boolean networks, IEEE Transactions on Automatic Control, 55, 10, 2251-2258 (2010) · Zbl 1368.37025
[23] Cheng, D.; Li, Z.; Qi, H., Realization of Boolean control networks, Automatica, 46, 1, 62-69 (2010) · Zbl 1214.93031
[24] Cheng, D., Disturbance decoupling of boolean control networks, IEEE Transactions on Automatic Control, 56, 1, 2-10 (2011) · Zbl 1368.93100
[25] Cheng, D.; Qi, H.; Li, Z.; Liu, J. B., Stability and stabilization of Boolean networks, International Journal of Robust and Nonlinear Control, 21, 2, 134-156 (2011) · Zbl 1213.93121
[26] Laschov, D.; Margaliot, M., A maximum principle for single-input Boolean control networks, IEEE Transactions on Automatic Control, 56, 4, 913-917 (2011) · Zbl 1368.93344
[27] Li, F.; Sun, J., Controllability of Boolean control networks with time delays in states, Automatica, 47, 3, 603-607 (2011) · Zbl 1220.93010
[28] Li, H.; Wang, Y., Boolean derivative calculation with application to fault detection of combinational circuits via the semi-tensor product method, Automatica, 48, 4, 688-693 (2012) · Zbl 1238.93029
[29] Liu, Z.; Wang, Y., Disturbance decoupling of mix-valued logical networks via the semi-tensor product method, Automatica, 48, 8, 1839-1844 (2012) · Zbl 1268.93104
[30] Feng, J.; Yao, J.; Cui, P., Singular Boolean networks: semi-tensor product approach, Science China Information Sciences, 56, 11, 1-14 (2013)
[31] Wang, Y.; Zhang, C.; Liu, Z., A matrix approach to graph maximum stable set and coloring problems with application to multi-agent systems, Automatica, 48, 7, 1227-1236 (2012) · Zbl 1246.93010
[32] Horn, R. A.; Johnson, C. R., Topics in Matrix Analysis, viii+607 (1991), Cambridge, Mass, USA: Cambridge University Press, Cambridge, Mass, USA
[33] Berge, C., Graphs and Hypergraphs, xiv+528 (1973), Amsterdam, The Netherlands: North-Holland, Amsterdam, The Netherlands
[34] Sotskov, Y. N.; Tanaev, V. S.; Werner, F., Scheduling problems and mixed graph colorings, Optimization, 51, 3, 597-624 (2002) · Zbl 1007.90027
[35] Al-Anzi, F. S.; Sotskov, Y. N.; Allahverdi, A.; Andreev, G. V., Using mixed graph coloring to minimize total completion time in job shop scheduling, Applied Mathematics and Computation, 182, 2, 1137-1148 (2006) · Zbl 1114.90033
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.