On some complexity properties of N-free posets and posets with bounded decomposition diameter
DOI10.1016/0012-365X(87)90006-9zbMATH Open0608.06004OpenAlexW2061209173MaRDI QIDQ1086264FDOQ1086264
Authors: M. A. Habib, Rolf H. Möhring 
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
Recommendations
- 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
isomorphism problemNP-hardcombinatorial optimization problemsscheduling problempolynomially solvableN-free posetsseries-parallel posetsjump-number problemposets with bounded decomposition diameter
Permutations, words, matrices (05A05) Partial orders, general (06A06) Deterministic scheduling theory in operations research (90B35) Free lattices, projective lattices, word problems (06B25)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Asymptotic Enumeration of Partial Orders on a Finite Set
- Complement reducible graphs
- Title not available (Why is that?)
- The Complexity of the Partial Order Dimension Problem
- Partially Ordered Sets
- Title not available (Why is that?)
- On the X-join decomposition for undirected graphs
- Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
- Title not available (Why is that?)
- Topology of series-parallel networks
- Title not available (Why is that?)
- Decomposition Algorithms for Single-Machine Sequencing with Precedence Relations and Deferral Costs
- Title not available (Why is that?)
- Minimizing the jump number for partially ordered sets: A graph-theoretic approach
- A Fast Algorithm for the Decomposition of Graphs and Posets
- Title not available (Why is that?)
- A structured program to generate all topological sorting arrangements
- Linear-time computation of optimal subgraphs of decomposable graphs
- Maximal chains and antichains
- Optimal Sequencing Via Modular Decomposition: Characterization of Sequencing Functions
- Linear-time computability of combinatorial problems on series-parallel graphs
- A V log V algorithm for isomorphism of triconnected planar graphs
- Minimizing Setups for Ordered Sets: A Linear Algebraic Approach
- Title not available (Why is that?)
- Almost all comparability graphs are UPO
- The Jump Number of Dags and Posets: An Introduction
- Ordres "C.A.C."
- N-free posets as generalizations of series-parallel posets
- A labeling algorithm to recognize a line digraph and output its root graph
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (22)
- On the computational complexity of the order polynomial
- N-free posets as generalizations of series-parallel posets
- Efficient polynomial algorithms for distributive lattices
- Relative Ockham lattices: their order-theoretic and algebraic characterisation
- Minimizing the jump number for partially-ordered sets: A graph-theoretic approach. II
- An algorithm for solving the jump number problem
- On some new types of greedy chains and greedy linear extensions of partially ordered sets
- Cross-series-parallel digraphs
- On the structure of trapezoid graphs
- Linear extensions of N-free orders.
- Counting linear extensions
- Transitive closure for restricted classes of partial orders
- Regularity of residuated mappings
- Triangulating multitolerance graphs
- On the Jump Number of Lexicographic Sums of Ordered Sets
- Counting Cherry reduction sequences in phylogenetic tree-child networks is counting linear extensions
- PLA folding in special graph classes
- The arboreal jump number of an order
- New bijective links on planar maps via orientations
- Asymptotic enumeration of N-free partial orders
- \(N\)-free orders and minimal interval extensions
- Counting linear extensions: parameterizations by treewidth
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)
