Parcours dans les graphes: Un outil pour l’algorithmique des ensembles ordonnés. (French) Zbl 0589.06004

Bordat, J. P.

Discrete Appl. Math. 12, 215-231 (1985).

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

Reviewer: J.Neggers (Tuscaloosa)

MSC:

06C10	Semimodular lattices, geometric lattices
06A06	Partial orders, general
68Q25	Analysis of algorithms and problem complexity
05C38	Paths and cycles

Keywords:

finite posets; algorithms; complexity; lower semi-modularity; upper semi- modularity; Hasse diagram

References:

[1]	Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Designs and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0286.68029
[2]	Avann, S. P., Application of the join-irreducible excess function to semi-modular lattices, Math. Ann., 142, 345-354 (1961) · Zbl 0094.01603
[3]	Barthelemy, J. P., Remarques sur les propriétés métriques des ensembles ordonnés, Math. Sci. Hum., 61, 39-60 (1978), 16e année · Zbl 0419.06001
[4]	Berge, C., Graphes et Hypergraphes (1970), Dunod: Dunod Paris · Zbl 0213.25702
[5]	Birkhoff, G., Lattice Theory, (Amer. Math. Soc., Vol. 25 (1967), AMS: AMS Providence, RI) · Zbl 0126.03801
[6]	Bordat, J. P., Complexité de problèmes liés aux graphes sans circuit (1984), CRIM: CRIM Montpellier, R.R., no. 9 · Zbl 0634.68031
[7]	Bordat, J. P.; Cazes, A.; Chein, M.; Cogis, O.; Guido, Y., C.A.B.R.I.: Première maquette d’un cahier de brouillon informatisé pour létude des ensembles ordonnés (1983), CRIM: CRIM Montpellier, R.R. no. 5
[8]	Bordat, J. P.; Cogis, O., Parcours dans les graphes sans circuit (1984), CRIM: CRIM Montpellier, soumis à Order
[9]	Goralcik, P.; Goralcikova, A.; Koubek, V., Fast recognition of rings and lattices, (Proceedings of FCT 81 (1981), Springer: Springer Berlin) · Zbl 0466.68035
[10]	Goralcikova, A.; Koubek, V., A reduct-and-closure algorithm for graphs, (Proceedings of MFCS 79 (1979), Springer: Springer Berlin), 301-307 · Zbl 0408.68038
[11]	M. Habib, M. Hamroun et R. Jegou, Linear equivalences for transitivity in graphs, Discrete Math., à paraître.; M. Habib, M. Hamroun et R. Jegou, Linear equivalences for transitivity in graphs, Discrete Math., à paraître.
[12]	Knuth, D. E., Big omicron and big omega and big theta, Sigact News, 18-24 (April-June, 1976)
[13]	Koubek, V.; Rodl, V., On number of covering arcs in ordering, Comm. Math. Univ. Carol., 22, 4, 721-733 (1981) · Zbl 0483.05035
[14]	Monjardet, B., Caractérisations métriques des ensembles ordonnés semi-modulaires, Math. Sci. Hum., 56, 77-87 (1976), 14e année · Zbl 0367.06010
[15]	V. Strassen, Gaussian elimination is not optimal, Num. Math. 13 (19) 354-356.; V. Strassen, Gaussian elimination is not optimal, Num. Math. 13 (19) 354-356. · Zbl 0185.40101
[16]	Tarjan, R. E., Space-efficient implementation of graph search methods, ACM Trans. Math. Soft., 9, 3, 326-339 (Sept. 1983) · Zbl 0525.68043
[17]	Wirth, N., Algorithms + Data Structures = Programs (1976), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0375.68005