ISGCI project home  All classes  Smallgraphs

Graphclass: unit tolerance

Definition:
A graph is a unit tolerance if it is a  tolerance  in which every interval is of unit length.

References: [462]
Related classes:  tolerance 

Inclusions

Minimal superclasses:  AT-free   (Cn+6,T2,X2,X3,X30,X31,X32,X33,X34,X35,X36,X37,X38,X39,X40,X41,XF2n+1,XF3n,XF4n)-free   alternately orientable   (anti-hole,hole)-free   circle-polygon   proper tolerance   spider graph   weakly chordal 
Maximal subclasses:  probe unit interval 

Problems summary

Recognition:Opendetails
Cliquewidth expression: Unbounded or NP-complete details
Cliquewidth:Unboundeddetails
Weighted independent set:Polynomialdetails
Independent set:Lineardetails
Domination:Polynomialdetails

Algorithms for Recognition

Open

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).

Polynomial [O(n^4)] from AT-free  [160]
Polynomial from interval filament  [1159]
Polynomial from perfect  [476]
Polynomial [O(V^4)] from weakly chordal  [997]
Polynomial from subtree overlap  [1123]
See also : Cliquewidth expression : Independent set

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]
See also : Cliquewidth expression