A Matrix Approach to Hypergraph Stable Set and Coloring Problems with Its Application to Storing Problem
Joint Authors
Source
Journal of Applied Mathematics
Issue
Vol. 2014, Issue 2014 (31 Dec. 2014), pp.1-9, 9 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2014-04-28
Country of Publication
Egypt
No. of Pages
9
Main Subjects
Abstract EN
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.
American Psychological Association (APA)
Meng, Min& Feng, Jun-e. 2014. A Matrix Approach to Hypergraph Stable Set and Coloring Problems with Its Application to Storing Problem. Journal of Applied Mathematics،Vol. 2014, no. 2014, pp.1-9.
https://search.emarefa.net/detail/BIM-497757
Modern Language Association (MLA)
Meng, Min& Feng, Jun-e. A Matrix Approach to Hypergraph Stable Set and Coloring Problems with Its Application to Storing Problem. Journal of Applied Mathematics No. 2014 (2014), pp.1-9.
https://search.emarefa.net/detail/BIM-497757
American Medical Association (AMA)
Meng, Min& Feng, Jun-e. A Matrix Approach to Hypergraph Stable Set and Coloring Problems with Its Application to Storing Problem. Journal of Applied Mathematics. 2014. Vol. 2014, no. 2014, pp.1-9.
https://search.emarefa.net/detail/BIM-497757
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-497757