a*.
The question is whether or not there is some placement of these detectors
a1, a2, ... , ak on the real line such that Sx`
forms a consecutive part among all detectors, for every vertex x.
Since intervals obey the
Helly-property,
all cliques in an
interval graph
are star graphs.
There are more star graphs, but we may neglect them in the remaining
layout step of the recognition algorithm; we may discretize.
Let a1*, a2*, ... , ak* be the cliques, and define
Sx` as the set of all those points a where
x a*.
The question is whether or not there is some placement of these detectors
a1, a2, ... , ak on the real line such that Sx`
forms a consecutive part among all detectors, for every vertex x.
A concrete interval hypergraph has vertex set {1,2, ... , n} and all hyperedges have the form {i,i+1, ... , j}. An interval hypergraph is any hypergraph isomorphic to some concrete interval hypergraph. So we have the hypergraph, but have forgotten the vertex labels. The question above is how to recognize interval hypergraphs. Surely we have no time to test all n! vertex labelings.
In matrix theory, this problem is known under the consecutive-ones problem. A 0-1 matrix has the consecutive-ones property for rows if the columns can be permuted in such a way that the ones in each row appear consecutively. A hypergraph is an interval hypergraph if and only if its incidence matrix has the consecutive-ones property for rows. It is possible, though rather involved, to recognize this property in linear time, but since this has few to do with intersection graphs, we will omit the proof.
[BL76]:
Interval hypergraphs can be recognized in linear time. |
Note that there are quite a few more characterizations leading to efficient recognition algorithms for interval graphs. In all of them, the linearity and ordering of the model is cruical.