Parcours dans les graphes: Un outil pour l'algorithmique des ensembles ordonnés (Q1073816)

It is the purpose of this paper to demonstrate how several theoretical characterizations of finite posets can be related to other such characterizations which have the addition advantange of being cast in a language which makes them available for checking via algorithms whose complexity reflects quite nicely the actual structure of the very posets being investigated. Such approaches to classification will no doubt become more and more popular. A property such as lower semi-modularity or its dual, upper semi-modularity, leads then to interesting alternative statements, which in this case are strengthened and specialized to yield examples of conditions for lattices, e.g., a lattice X is modular if and only if its Hasse diagram graph is such that whenever \(r(x)=r(y)\) (rank), then \(\lambda (x,y)=0\) \((\lambda (x,y)=r(x\vee y)+r(x\wedge y)-r(x)- r(y))\), which from the constructions made in the paper can be seen to be verifiable with complexity \(O(| X|^ 2)\).