On some complexity properties of N-free posets and posets with bounded decomposition diameter
From MaRDI portal
Publication:1086264
DOI10.1016/0012-365X(87)90006-9zbMath0608.06004MaRDI QIDQ1086264
Rolf H. Möhring, Michel A. Habib
Publication date: 1987
Published in: Discrete Mathematics (Search for Journal in Brave)
NP-hard; isomorphism problem; combinatorial optimization problems; scheduling problem; polynomially solvable; N-free posets; series-parallel posets; jump-number problem; posets with bounded decomposition diameter
06A06: Partial orders, general
05A05: Permutations, words, matrices
90B35: Deterministic scheduling theory in operations research
06B25: Free lattices, projective lattices, word problems
Related Items
On the Jump Number of Lexicographic Sums of Ordered Sets, Efficient polynomial algorithms for distributive lattices, Asymptotic enumeration of N-free partial orders, 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, On some new types of greedy chains and greedy linear extensions of partially ordered sets, On the structure of trapezoid graphs, Regularity of residuated mappings, Relative Ockham lattices: their order-theoretic and algebraic characterisation
Cites Work
- Almost all comparability graphs are UPO
- 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
- Complement reducible graphs
- 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
- Topology of series-parallel networks
- The Complexity of the Partial Order Dimension Problem
- A Fast Algorithm for the Decomposition of Graphs and Posets
- Minimizing Setups for Ordered Sets: A Linear Algebraic Approach
- Optimal Sequencing Via Modular Decomposition: Characterization of Sequencing Functions
- The Jump Number of Dags and Posets: An Introduction
- Linear-time computability of combinatorial problems on series-parallel graphs
- Asymptotic Enumeration of Partial Orders on a Finite Set
- Decomposition Algorithms for Single-Machine Sequencing with Precedence Relations and Deferral Costs
- Ordres "C.A.C."
- Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
- Linear-time computation of optimal subgraphs of decomposable graphs
- Maximal chains and antichains
- Partially Ordered Sets
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item