<p>Here is a link, may be it can help you. <a href="http://fc.isima.fr/~nourine/publications.php" rel="nofollow noreferrer">http://fc.isima.fr/~nourine/publications.php</a>
M. Habib and L. Nourine : A Linear Time Algorithm to Recognize Distributive Lattices, RR LIRMM, No 92-012, 1992.</p>

CC BY-SA 4.0
2019-08-19T17:24:53.890Z
2019-08-19T17:24:53.890Z
user53561
<p>Re your questions (2+4): an undirected graph G is the covering graph (not the comparability graph!) of a distributed lattice iff it is a <a href="http://en.wikipedia.org/wiki/Median_graph" rel="noreferrer">median graph</a> and it has two vertices that are complementary (on opposite sides of each Djokovic equivalence class of edges); see Duffus, Dwight; Rival, Ivan (1983), "Graphs orientable as distributive lattices", Proc. AMS 88 (2): 197–200. This can be turned into an efficient algorithm by combining a median graph recognition algorithm (see the Wikipedia article) with an algorithm for finding complementary pairs of vertices (see theorem 3 of <a href="http://arxiv.org/abs/cs.DS/0206033" rel="noreferrer">arxiv:cs.DS/0206033</a>).</p>

CC BY-SA 3.0
2011-05-21T03:12:25.863Z
2011-05-21T03:12:25.863Z
David Eppstein
<p>There has been a fair amount of work on computational problems for partial orders (e.g., recognition, jump number, comparability graph recognition, etc...).</p>

<p>I am curious what work specific to lattices has been done. I have searched around and not found much similar work for lattices. </p>

<p>In particular, I am interested in whether the following lattice problems have been investigated:</p>

<ol>
<li><p>Lattice recognition: given a DAG or a partial order is it in fact a lattice?</p></li>
<li><p>Lattice comparability graph recognition: given a undirected graph G, can the edges of G be oriented such that the resulting orientation is a lattice?</p></li>
<li><p>Determining/counting the join irreducible elements of a lattice</p></li>
<li><p>Determining if a given lattice is distributed/modular</p></li>
</ol>

CC BY-SA 3.0
2011-05-23T07:02:00.877Z
a related question: suppose the lattice is not presented explicitly, but via (say) a neighborhood oracle (in and out)
Suresh Venkat
<ds.algorithms><reference-request><graph-algorithms><partial-order><order-theory>
Lattice problems
Travis Service
# Lattice problems

(Asked by: username_0 on 2011-05-20)

There has been a fair amount of work on computational problems for partial orders (e.g., recognition, jump number, comparability graph recognition, etc...).

I am curious what work specific to lattices has been done. I have searched around and not found much similar work for lattices.

In particular, I am interested in whether the following lattice problems have been investigated:

1. Lattice recognition: given a DAG or a partial order is it in fact a lattice?
2. Lattice comparability graph recognition: given a undirected graph G, can the edges of G be oriented such that the resulting orientation is a lattice?
3. Determining/counting the join irreducible elements of a lattice
4. Determining if a given lattice is distributed/modular

**Tags:** ds.algorithms, reference-request, graph-algorithms, partial-order, order-theory

> **Comments:**
> **username_1**: a related question: suppose the lattice is not presented explicitly, but via (say) a neighborhood oracle (in and out)  

---

## 2 answers

### Answer by username_3 on 2011-05-21. Score: 16 | Accepted answer

Re your questions (2+4): an undirected graph G is the covering graph (not the comparability graph!) of a distributed lattice iff it is a [median graph](http://en.wikipedia.org/wiki/Median_graph) and it has two vertices that are complementary (on opposite sides of each Djokovic equivalence class of edges); see Duffus, Dwight; Rival, Ivan (1983), "Graphs orientable as distributive lattices", Proc. AMS 88 (2): 197–200. This can be turned into an efficient algorithm by combining a median graph recognition algorithm (see the Wikipedia article) with an algorithm for finding complementary pairs of vertices (see theorem 3 of [arxiv:cs.DS/0206033](http://arxiv.org/abs/cs.DS/0206033)).


---

### Answer by username_2 on 2019-08-19. Score: 1

Here is a link, may be it can help you. <http://fc.isima.fr/~nourine/publications.php>
M. Habib and L. Nourine : A Linear Time Algorithm to Recognize Distributive Lattices, RR LIRMM, No 92-012, 1992.


---

