On some complexity properties of N-free posets and posets with bounded decomposition diameter

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)

zbMATH Keywords

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

Mathematics Subject Classification ID

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