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

DOI10.1016/0012-365X(87)90006-9zbMath0608.06004OpenAlexW2061209173MaRDI QIDQ1086264

Rolf H. Möhring, Michel A. Habib

Publication date: 1987

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(87)90006-9

zbMATH Keywords

NP-hardisomorphism problemcombinatorial optimization problemsscheduling problempolynomially solvableN-free posetsseries-parallel posetsjump-number problemposets with bounded decomposition diameter

Mathematics Subject Classification ID

Partial orders, general (06A06) Permutations, words, matrices (05A05) Deterministic scheduling theory in operations research (90B35) Free lattices, projective lattices, word problems (06B25)

Related Items

PLA folding in special graph classes, On the computational complexity of the order polynomial, On some new types of greedy chains and greedy linear extensions of partially ordered sets, 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, On the structure of trapezoid graphs, Triangulating multitolerance graphs, The arboreal jump number of an order, Asymptotic enumeration of N-free partial orders, Transitive closure for restricted classes of partial orders, Counting linear extensions, Counting linear extensions: parameterizations by treewidth, Cross-series-parallel digraphs, \(N\)-free orders and minimal interval extensions, Relative Ockham lattices: their order-theoretic and algebraic characterisation, Regularity of residuated mappings, On the Jump Number of Lexicographic Sums of Ordered Sets, New bijective links on planar maps via orientations, Efficient polynomial algorithms for distributive lattices, Linear extensions of N-free orders.

Cites Work

• 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
• 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