Complexity of representation of graphs by set systems |
| |
Authors: | Svatopluk Poljak Vojtěch Rödl Daniel Turzík |
| |
Affiliation: | KZAA, MFFUK, Sokolovská 83, 180 000 Praha 8, Czechoslovakia |
| |
Abstract: | Let be a family of subsets of S and let G be a graph with vertex set such that: (xA, xB) is an edge iff . The family is called a set representation of the graph G.It is proved that the problem of finding minimum k such that G can be represented by a family of sets of cardinality at most k is NP-complete. Moreover, it is NP-complete to decide whether a graph can be represented by a family of distinct 3-element sets.The set representations of random graphs are also considered. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|