A Matrix Approach to Hypergraph Stable Set and Coloring Problems with Its Application to Storing Problem
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 c...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2014-01-01
|
| Series: | Journal of Applied Mathematics |
| Online Access: | http://dx.doi.org/10.1155/2014/783784 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| 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. |
|---|---|
| ISSN: | 1110-757X 1687-0042 |