On some complexity properties of N-free posets and posets with bounded decomposition diameter
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.
- On the diameter and girth of zero-divisor graphs of posets
- The Complexity of the Extendibility Problem for Finite Posets
- Nonuniform complexity classes, decision graphs and homological properties of posets
- Progress on poset-free families of subsets
- Computing the dimension of N-free ordered sets is NP-complete
- On the dimension of posets with cover graphs of treewidth 2
- scientific article; zbMATH DE number 3995740
- Improved bound for the dimension of posets of treewidth two
- On the complexity of cover-incomparability graphs of posets
- scientific article; zbMATH DE number 1759433
- A Fast Algorithm for the Decomposition of Graphs and Posets
- A labeling algorithm to recognize a line digraph and output its root graph
- A structured program to generate all topological sorting arrangements
- A V log V algorithm for isomorphism of triconnected planar graphs
- Almost all comparability graphs are UPO
- Asymptotic Enumeration of Partial Orders on a Finite Set
- Complement reducible graphs
- Decomposition Algorithms for Single-Machine Sequencing with Precedence Relations and Deferral Costs
- scientific article; zbMATH DE number 3860892 (Why is no real title available?)
- scientific article; zbMATH DE number 3877241 (Why is no real title available?)
- scientific article; zbMATH DE number 3896963 (Why is no real title available?)
- scientific article; zbMATH DE number 3906240 (Why is no real title available?)
- scientific article; zbMATH DE number 3908482 (Why is no real title available?)
- scientific article; zbMATH DE number 3675952 (Why is no real title available?)
- scientific article; zbMATH DE number 3757695 (Why is no real title available?)
- scientific article; zbMATH DE number 3786844 (Why is no real title available?)
- scientific article; zbMATH DE number 3485834 (Why is no real title available?)
- scientific article; zbMATH DE number 3558962 (Why is no real title available?)
- scientific article; zbMATH DE number 3641455 (Why is no real title available?)
- scientific article; zbMATH DE number 3449757 (Why is no real title available?)
- scientific article; zbMATH DE number 3893249 (Why is no real title available?)
- scientific article; zbMATH DE number 3894817 (Why is no real title available?)
- scientific article; zbMATH DE number 3218572 (Why is no real title available?)
- Linear-time computability of combinatorial problems on series-parallel graphs
- Linear-time computation of optimal subgraphs of decomposable graphs
- Maximal chains and antichains
- Minimizing Setups for Ordered Sets: A Linear Algebraic Approach
- Minimizing the jump number for partially ordered sets: A graph-theoretic approach
- N-free posets as generalizations of series-parallel posets
- On the X-join decomposition for undirected graphs
- Optimal Sequencing Via Modular Decomposition: Characterization of Sequencing Functions
- Ordres "C.A.C."
- Partially Ordered Sets
- Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
- The Complexity of the Partial Order Dimension Problem
- The Jump Number of Dags and Posets: An Introduction
- Topology of series-parallel networks
- New bijective links on planar maps via orientations
- On the computational complexity of the order polynomial
- N-free posets as generalizations of series-parallel posets
- Minimizing the jump number for partially-ordered sets: A graph-theoretic approach. II
- An algorithm for solving the jump number problem
- Transitive closure for restricted classes of partial orders
- Counting linear extensions
- \(N\)-free orders and minimal interval extensions
- PLA folding in special graph classes
- Triangulating multitolerance graphs
- Counting linear extensions: parameterizations by treewidth
- On some new types of greedy chains and greedy linear extensions of partially ordered sets
- On the structure of trapezoid graphs
- The arboreal jump number of an order
- Cross-series-parallel digraphs
- Regularity of residuated mappings
- Linear extensions of N-free orders.
- Relative Ockham lattices: their order-theoretic and algebraic characterisation
- scientific article; zbMATH DE number 1161260 (Why is no real title available?)
- On the Jump Number of Lexicographic Sums of Ordered Sets
- Counting Cherry reduction sequences in phylogenetic tree-child networks is counting linear extensions
- Efficient polynomial algorithms for distributive lattices
- Asymptotic enumeration of N-free partial orders
This page was built for publication: On some complexity properties of N-free posets and posets with bounded decomposition diameter
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1086264)
