On some new types of greedy chains and greedy linear extensions of partially ordered sets (Q1894377): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Minimizing setups in ordered sets of fixed width / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On some complexity properties of N-free posets and posets with bounded decomposition diameter / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: NP-completeness results concerning greedy and super greedy linear extensions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Optimal Linear Extensions by Interchanging Chains / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Minimizing the jump number for partially-ordered sets: A graph-theoretic approach. II / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An algorithm for solving the jump number problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The jump number problem on interval orders: A 3/2 approximation algorithm / rank | |||
Normal rank |
Latest revision as of 15:51, 23 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On some new types of greedy chains and greedy linear extensions of partially ordered sets |
scientific article |
Statements
On some new types of greedy chains and greedy linear extensions of partially ordered sets (English)
0 references
13 December 1995
0 references
The author's presence in both practical as well as theoretical aspects of research into the details of the jump number problem has been long established. In this paper the author provides an insightful theoretical discussion concerning the role that strongly greedy and semi-strongly greedy chains (defined here also) play in the construction of greedy linear extensions which deform to those from which the jump number may be more efficiently determined by restricting the search space for any (suitable) algorithm. Thus Theorem 1: If a poset \(P\) contains a strongly greedy chain \(C\), then every greedy linear extension \(L\) of \(P\) can be transformed to a greedy linear extension \(L^*\) of \(P\) which begins with \(C\) and such that \(S(P, L^*)\leq S(P,L)\) (the jump number). This leads to: Corollary 1. If a poset \(P\) contains a strongly greedy chain \(C\), then \(P\) has an optimal linear extension which begins with \(C\) and such that \(S(P)= S(P- C)+1\). Theorem 2: If a poset \(P\) has no strongly greedy chain, then it has a semi-strongly greedy chain, establishes a branching whence. Theorem 3 becomes Theorem 1 for the semi-strongly greedy chain case. For those interested in the structure theory of (finite) posets the discussion in this paper is possibly most relevant because of perspectives on additional refined classifications going beyond being series-parallel or \(N\)-free, for example, to classes also sufficiently well-defined to permit the establishment of otherwise NP-complete algorithms as being polynomial-time. The fact that this is so suggests that useful invariants may be associated with such classes. As observed by the author one such is a non-\(N\)-freeness degree directly useful in complexity estimations which will also put limits on other parameters associated with posets.
0 references
complexity
0 references
jump number
0 references
greedy chains
0 references
greedy linear extensions
0 references
algorithm
0 references
0 references