The Complexity of the Partial Order Dimension Problem
From MaRDI portal
Cites work
- Characterization problems for graphs, partially ordered sets, lattices, and families of sets
- Computing the Minimum Fill-In is NP-Complete
- scientific article; zbMATH DE number 3172309 (Why is no real title available?)
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3598234 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 3307331 (Why is no real title available?)
- scientific article; zbMATH DE number 3318560 (Why is no real title available?)
- Intransitive indifference with unequal indifference intervals
- On the complexity of posets
- Partially Ordered Sets
- Quantum private communication
- Some simplified NP-complete graph problems
- Sufficient Conditions for Graphs to Have Threshold Number 2
- The 3-Irreducible Partially Ordered Sets
- Transitive Orientation of Graphs and Identification of Permutation Graphs
Cited in
(only showing first 100 items - show all)- Cubicity, boxicity, and vertex cover
- Cubicity of threshold graphs
- An upper bound for cubicity in terms of boxicity
- Localized and compact data-structure for comparability graphs
- Boxicity of Halin graphs
- On the cubicity of certain graphs
- On the cubicity of interval graphs
- On realizable biorders and the biorder dimension of a relation
- Interval graphs and related topics
- The complexity of facets (and some facets of complexity)
- Decomposing weighted digraphs into sums of chains
- On some complexity properties of N-free posets and posets with bounded decomposition diameter
- On finding the bidimension of a relation
- Multidimensional scaling and threshold graphs
- Strict 2-threshold graphs
- Trapezoid graphs and their coloring
- Algorithmic aspects of intersection graphs and representation hypergraphs
- Planar graphs and poset dimension
- Asymptotic enumeration of two-dimensional posets
- Comparability graphs and intersection graphs
- An appraisal of computational complexity for operations researchers
- The interval inclusion number of a partially ordered set
- Split dimension of graphs
- Transitive closure for restricted classes of partial orders
- \(N\)-free orders and minimal interval extensions
- On the complexity of the k-chain subgraph cover problem
- Some complexity results about threshold graphs
- A special planar satisfiability problem and a consequence of its NP- completeness
- On treewidth and minimum fill-in of asteroidal triple-free graphs
- Soft dimension theory.
- Searching for the dimension of valued preference relations.
- On variations of \(P_{4}\)-sparse graphs
- Powers of geometric intersection graphs and dispersion algorithms
- On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
- Induced matchings in asteroidal triple-free graphs
- \(P_{5}\)-free augmenting graphs and the maximum stable set problem
- Some results on maximum stable sets in certain \(P_{5}\)-free graphs
- The order dimension of the poset of regions in a hyperplane arrangement.
- (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
- Dimension of valued relations
- FO model checking on geometric graphs
- Co-bipartite neighborhood edge elimination orderings
- Sublinear approximation algorithms for boxicity and related problems
- On dynamic threshold graphs and related classes
- One-sided weak dominance drawing
- Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications
- On the structure of (\(P_{5}\),\,gem)-free graphs
- Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width
- On the generation of circuits and minimal forbidden sets
- Fractional dimension of partial orders
- Computing the dimension of N-free ordered sets is NP-complete
- Geometrical embeddings of graphs
- A recognition algorithm for orders of interval dimension two
- Enumeration of difference graphs
- On edge transitivity of directed graphs
- On the geometric separability of Boolean functions
- Cubicity and bandwidth
- Timestamping messages and events in a distributed system using synchronous communication
- On the vertex ranking problem for trapezoid, circular-arc and other graphs
- Representing graphs as the intersection of cographs and threshold graphs
- On list \(k\)-coloring convex bipartite graphs
- Role coloring bipartite graphs
- On bipartite graphs having minimum fourth adjacency coefficient
- Tight bounds to localize failure nodes on trees, grids and through embeddings under Boolean network tomography
- The complexity of the defensive domination problem in special graph classes
- \(k\)-majority digraphs and the hardness of voting with a constant number of voters
- Fast algorithms for computing the characteristic polynomial of threshold and chain graphs
- Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity
- Lower bounds for boxicity
- Paretian partial orders: the two-agent case
- The fixed point property for ordered sets of interval dimension 2
- Chronological rectangle digraphs which are two-terminal series-parallel
- Finite dimensional scattered posets
- On the complexity of the black-and-white coloring problem on some classes of perfect graphs
- Boxicity and maximum degree
- On the interval completion of chordal graphs
- Cubicity, degeneracy, and crossing number
- On multipartite posets
- Embedding ordered sets into distributive lattices
- Boxicity and treewidth
- Dimension invariance of subdivisions
- Fully dynamically maintaining minimal integral separator for threshold and difference graphs
- On maximal chain subgraphs and covers of bipartite graphs
- A characterization of the n-agent Pareto dominance relation
- Cubicity of interval graphs and the claw number
- Mining posets from linear orders.
- Ranking chain sum orders
- Rainbow connection number and connected dominating sets
- An \(O(n^3)\) time algorithm for recognizing threshold dimension 2 graphs
- Vertex ranking of asteroidal triple-free graphs
- Large Induced Subgraphs via Triangulations and CMSO
- The complexity of the partial order dimension problem: closing the gap
- Secure authenticated comparisons
- Steiner transitive-closure spanners of low-dimensional posets
- Bounds on Threshold Dimension and Disjoint Threshold Coverings
- Cubicity of interval graphs and the claw number
- Alternation graphs
- Threshold Dimension of Graphs
- Succinct posets
- Minors and dimension
This page was built for publication: The Complexity of the Partial Order Dimension Problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3663349)
