Greedy linear extensions to minimize jumps (Q1061150): Difference between revisions
From MaRDI portal
Created a new Item |
Set OpenAlex properties. |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / author | |||
Property / author: Mohamed H. El-Zahar / rank | |||
Property / author | |||
Property / author: Ivan Rival / rank | |||
Property / author | |||
Property / author: Mohamed H. El-Zahar / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Ivan Rival / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4200070 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the size of jump-critical ordered sets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Optimal Linear Extensions by Interchanging Chains / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/s0166-218x(85)80005-6 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2056816149 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 11:54, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Greedy linear extensions to minimize jumps |
scientific article |
Statements
Greedy linear extensions to minimize jumps (English)
0 references
1985
0 references
The problem of linear extensions of (partially) ordered sets has received much attention lately. Let P be an ordered set of n elements and L(P) the set of all its linear extensions, i.e. linear (total) orders on P respecting the given order relation. A ''jump'' is the occurence of two elements p,q in a linear extension, p covering q, but \(p\ngeq q\) in the original order. Call S(P) the minimal number of jumps taken over L(P). A linear extension of P is called optimal if its number of jumps is equal to S(P). Among others, there are two main problems concerning S(P) and O(P): find an algorithm to determine S(P) and one for constructing elements of O(P). The first problem has recently been shown to be NP-hard by W. R. Pulleyblank. For the second problem, one has devised a greedy algorithm, leading to a set G(P) of linear extensions of P. In general neither of O(P) and G(P) need contain the other, so it becomes an important question to find conditions for P that allow statements about the connection between O(P) and G(P). The second author has proved that \(G(P)=O(P)\) in case P is N-free, where N is a well-known ordered set of 4 elements. The present paper shows in Theorem 1 that O(P)\(\subseteq G(P)\) in case P does not contain an ordered \(2n+1\)-set usually called a ''fence''. Two other theorems are concerned with combinatorial rather than algorithmic problems. It is very unfortunate that the authors use the letter \(C_ n\) for n- chains (as usual), but also for the exceptional sets mentioned above. This makes reading of their paper especially troublesome.
0 references
jump number
0 references
optimal extension
0 references
linear extensions
0 references
ordered sets
0 references
jumps
0 references
greedy algorithm
0 references