A Survey of the Algorithmic Properties of Simplicial, Upper Bound and Middle Graphs <s> NP-C chromatic index <s> Two species in an ecosystem compete if and only if they have intersecting ecological niches. Competition can be defined independently by using a food web for the ecosystem, and this notion of competition gives rise to a competition graph. This paper briefly describes the problem of representing the competition graph as an intersection graph of boxes (k-dimensional rectangles representing ecological niches) in Euclidean k-space and then discusses the class of graphs which arise as competition graphs of (acyclic) food webs. <s> BIB001 </s> A Survey of the Algorithmic Properties of Simplicial, Upper Bound and Middle Graphs <s> NP-C chromatic index <s> A device for intermittently tensioning a yarn passing therethrough in which a motor cam acts on a tension train mounted on a fixed shaft. The tension train is composed of a tension adjuster which provides tension on a base plate, spring, and tension discs mounted between a stop and the tension adjuster. In an embodiment of the invention a method for intermittently tensioning a yarn by passing the yarn between the tension discs of the device described above. <s> BIB002
?? ?? ?? ?? NP-C dominating set NP-C NP-C NP-C n 1.5 + e NP-C edge dominating set n 0.5 * e n 0.5 * e n 0.5 * e n 0.5 * e NP-C maximum minimal dominating set n + e n + e n + e n + e NP-C irredundant set NP-C n + e n + e n + e NP-C minimum dominating independent set NP-C NP-C NP-C n 1.5 + e NP-C minimum maximal irredundant set NP-C NP-C NP-C n 1.5 + e NP-C hamiltonian path NP-C NP-C NP-C NP-C NP-C induced path NP-C NP-C NP-C NP-C NP-C graph isomorphism ISO-C ISO-C ISO-C ISO-C ISO-C subgraph isomorphism NP-C NP-C NP-C NP-C NP-C steiner tree NP-C NP-C NP-C NP-C NP-C simple maximum cut NP-C ?? ?? n + e n + e n = number of vertices in the graph e = number of edges in the graph s = number of simplices in the graph p = number of vertices in the root graph NP-C stands for NP-complete ISO-C stands for isomorphism-complete A graph is called simplicial  if every vertex is contained in a simplex, i.e., every vertex is either simplicial or adjacent to a simplicial vertex. Similarly, a graph is called edge simplicial if every edge is contained in a simplex. It turns out that the edge simplicial class is the same as the class of upper bound graphs. If (P, ≤) is a partially ordered set (poset), the upper bound graph BIB002 of P , G = (V, E), is defined as follows: V = P , and (x, y) ∈ E if and only if x = y and there exists a z ∈ P such that x ≤ z and y ≤ z. The proof of equivalence of these two classes  is based on the simplicial vertex of a simplex corresponding to the greatest upper bound of the same items in the poset. If instead of a partial order on P , there is a quasi-order (an irreflexive and transitive relation) on P , then instead of obtaining an upper bound graph, a strict upper bound graph BIB002 is obtained. For the quasi-order that corresponds to a given partial order, the edges of the strict upper bound graph are a strict subset of those of the upper bound graph. The strict upper bound class is a subclass of the class of competition graphs BIB001 that has been used in food web models of ecosystems. However, the strict upper bound and competition graph classes are incomparable with the class of upper bound graphs as each has members not in the upper bound class and vise versa. Of course, the simplicial class includes all upper bound (edge simplicial) graphs. We also consider classes of graphs that are contained in the upper bound class. We begin by recalling that a hypergraph  , H = (V, E), consists of a set of vertices V and a collection of edges E, where each edge is an arbitrary non-empty subset of V . If the sets in E are distinct, then H is called a simple hypergraph. From each hypergraph H, we can obtain a graph, Ω(H), called the representative graph of H. Ω(H) is the graph where its vertices are the edges of H, and two vertices are adjacent in Ω(H) if they have a non-empty intersection (as sets of V ). Hence, Ω(H) is the intersection graph of the edge set of H. Not only is Ω(H) a graph, but every (simple) graph is the representative graph of some hypergraph. However, we are interested in a subclass of the upper bound class. To get such a subclass, we need to consider hereditary hypergraphs  . A hypergraph H = (V, E) is called hereditary if e 1 ∈ E, e 2 ⊆ e 1 , and e 2 = ∅, then e 2 ∈ E.