On some complexity properties of N-free posets and posets with bounded decomposition diameter
type: Item
instance of: scholarly article
title: On some complexity properties of N-free posets and posets with bounded decomposition diameter
zbMATH Open document ID: 0608.06004
DOI: 10.1016/0012-365X(87)90006-9
published in: Discrete Mathematics
publication date: 1987-01-01T00:00:00Z
review text: Among generalizations of series-parallel posets, the N-free posets are much better known than posets with bounded decomposition diameter, i.e., those posets iteratively built up by substitution from posets of cardinality at most k. Nevertheless, the authors demonstrate that the latter class may well be the better one for a variety of combinatorial optimization problems and other reasons. Thus, although the jump-number problem is shown to be polynomially solvable on both classes, the isomorphism problem and the 1/prec/\(\sum w_ jC_ j\) scheduling problem are here demonstrated to be among these which are only polynomially solvable for the second class. As an early exponent of the merits of the substitution technique, this author finds the success of the method more than only interesting. Since the subject is still in a process of evolving its main outlines, this paper will make an important difference in the direction of eventual development. To the extent that it will be superseded by further results, its very success will make its view more commonplace.
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 05A05
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 06B25
zbMATH DE Number: 3983231
zbMATH Keywords: NP-hard
zbMATH Keywords: series-parallel posets
zbMATH Keywords: N-free posets
zbMATH Keywords: posets with bounded decomposition diameter
zbMATH Keywords: combinatorial optimization problems
zbMATH Keywords: jump-number problem
zbMATH Keywords: polynomially solvable
zbMATH Keywords: isomorphism problem
zbMATH Keywords: scheduling problem
author: M. A. Habib
author: Rolf H. Möhring
reviewed by: J. Neggers
MaRDI profile type: Publication
cites work: Q4773298
cites work: Linear-time computation of optimal subgraphs of decomposable graphs
cites work: A Fast Algorithm for the Decomposition of Graphs and Posets
cites work: Q4068748
cites work: The Jump Number of Dags and Posets: An Introduction
cites work: Q4200070
cites work: Complement reducible graphs
cites work: Topology of series-parallel networks
cites work: Partially Ordered Sets
cites work: Q3329227
cites work: Minimizing Setups for Ordered Sets: A Linear Algebraic Approach
cites work: Maximal chains and antichains
cites work: Q5184948
cites work: N-free posets as generalizations of series-parallel posets
cites work: On the X-join decomposition for undirected graphs
cites work: Q3872508
cites work: Q5345642
cites work: A V log V algorithm for isomorphism of triconnected planar graphs
cites work: Q3964626
cites work: Asymptotic Enumeration of Partial Orders on a Finite Set
cites work: A structured program to generate all topological sorting arrangements
cites work: Q4130999
cites work: Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
cites work: Q3940839
cites work: Ordres "C.A.C."
cites work: Almost all comparability graphs are UPO
cites work: Q3686754
cites work: Q3683903
cites work: Q5187059
cites work: Optimal Sequencing Via Modular Decomposition: Characterization of Sequencing Functions
cites work: Q3344241
cites work: Decomposition Algorithms for Single-Machine Sequencing with Precedence Relations and Deferral Costs
cites work: A labeling algorithm to recognize a line digraph and output its root graph
cites work: Minimizing the jump number for partially ordered sets: A graph-theoretic approach
cites work: Q3676161
cites work: Linear-time computability of combinatorial problems on series-parallel graphs
cites work: The Complexity of the Partial Order Dimension Problem
full work available at URL: 0012-365x(87)90006-9
OpenAlex ID: W2061209173
Recommended article: On the diameter and girth of zero-divisor graphs of posets
Recommended article: The Complexity of the Extendibility Problem for Finite Posets
Recommended article: Nonuniform complexity classes, decision graphs and homological properties of posets
Recommended article: Progress on poset-free families of subsets
Recommended article: Computing the dimension of N-free ordered sets is NP-complete
Recommended article: On the dimension of posets with cover graphs of treewidth 2
Recommended article: Q4723783
Recommended article: Improved bound for the dimension of posets of treewidth two
Recommended article: On the complexity of cover-incomparability graphs of posets
Recommended article: Q4536382
description: scientific article; zbMATH DE number 3983231