Definition:
A graph is a
probe unit interval graph
if its vertex set can be partitioned into two sets, probes (P)
and non-probes (N), such that N is independent and new edges can
be added between non-probes in such a way that the resulting
graph is a
unit interval graph.
comparability co-perfectly orderable intersection graphs of parallelograms (squares) probe interval unit tolerance 
chordal astral triple-free chordal unit circular arc claw-free interval indifference proper interval unit interval | Recognition: | Unknown to ISGCI | details |
| Cliquewidth expression: | Unbounded or NP-complete | details |
| Cliquewidth: | Unbounded | details |
| Weighted independent set: | Polynomial | details |
| Independent set: | Linear | details |
| Domination: | Polynomial | details |
Algorithms for Cliquewidth expression
See also
: Cliquewidth : Weighted independent set : Domination
Algorithms for Cliquewidth
Unbounded from unit interval
[1177]
See also
: Cliquewidth expression
Algorithms for Weighted independent set
Polynomial [O(n logn logn)]
from trapezoid
| Timebound valid only when given the model [1120] ; otherwise O(n^2). |
Algorithms for Independent set
Linear from co-comparability
[1100]
Polynomial [O(VE)]
from weakly chordal
[530]
[1119]
See also
: Weighted independent set
Algorithms for Domination
Polynomial from co-comparability
[1150]
[1151]
Polynomial from AT-free
[1152]
Polynomial from trapezoid
[1155]
Polynomial from probe interval
[1340]
See also
: Cliquewidth expression