Parcours dans les graphes: Un outil pour l'algorithmique des ensembles ordonnés (Q1073816): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
(One intermediate revision by one other user not shown) | |||
Property / cites work | |||
Property / cites work: Q4773298 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Application of the join-irreducible excess function to semi-modular lattices / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3852233 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5615282 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5331549 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Complexité de problèmes liés aux graphes sans circuit / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3919077 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4195940 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3941437 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4143354 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Gaussian elimination is not optimal / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Space-Efficient Implementations of Graph Search Methods / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4154035 / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0166-218x(85)90026-5 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2033624593 / rank | |||
Normal rank |
Latest revision as of 08:25, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Parcours dans les graphes: Un outil pour l'algorithmique des ensembles ordonnés |
scientific article |
Statements
Parcours dans les graphes: Un outil pour l'algorithmique des ensembles ordonnés (English)
0 references
1985
0 references
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)\).
0 references
finite posets
0 references
algorithms
0 references
complexity
0 references
lower semi-modularity
0 references
upper semi- modularity
0 references
Hasse diagram
0 references