On some new types of greedy chains and greedy linear extensions of partially ordered sets
type: Item
instance of: scholarly article
title: On some new types of greedy chains and greedy linear extensions of partially ordered sets
zbMATH Open document ID: 0827.06003
DOI: 10.1016/0166-218X(94)00065-L
published in: Discrete Applied Mathematics
publication date: 1995-12-13T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 06A07
Mathematics Subject Classification ID: 68Q99
zbMATH DE Number: 777838
zbMATH Keywords: complexity
zbMATH Keywords: jump number
zbMATH Keywords: greedy chains
zbMATH Keywords: greedy linear extensions
zbMATH Keywords: algorithm
author: Maciej M. Sysło
reviewed by: J. Neggers
MaRDI profile type: Publication
cites work: Minimizing setups in ordered sets of fixed width
cites work: On some complexity properties of N-free posets and posets with bounded decomposition diameter
cites work: NP-completeness results concerning greedy and super greedy linear extensions
cites work: Optimal Linear Extensions by Interchanging Chains
cites work: Minimizing the jump number for partially-ordered sets: A graph-theoretic approach. II
cites work: An algorithm for solving the jump number problem
cites work: The jump number problem on interval orders: A 3/2 approximation algorithm
description: scientific article; zbMATH DE number 777838