Abstract
In this paper we give two characterisations of the class of reflexive graphs admitting distributive lattice polymorphisms and use these characterisations to address the problem of recognition: we find a polynomial time algorithm to decide if a given reflexive graph G, in which no two vertices have the same neighbourhood, admits a distributive lattice polymorphism.
| Original language | English |
|---|---|
| Pages (from-to) | 81-105 |
| Number of pages | 25 |
| Journal | Bulletin of the Korean Mathematical Society |
| Volume | 55 |
| Issue number | 1 |
| DOIs | |
| State | Published - 2018 |
Keywords
- CSP
- Distributive lattice
- Lattice polymorphism
- Recognition
- Reflexive graph