The Complexity of the Partial Order Dimension Problem
From MaRDI portal
Publication:3663349
Cites work
- 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?)
- Characterization problems for graphs, partially ordered sets, lattices, and families of sets
- Computing the Minimum Fill-In is NP-Complete
- 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)- The Hardness of Approximating Poset Dimension
- Trapezoid graphs and their coloring
- Comparability graphs and intersection graphs
- A recognition algorithm for orders of interval dimension two
- Dimension-2 poset competition numbers and dimension-2 poset double competition numbers
- The hardness of approximating the boxicity, cubicity and threshold dimension of a graph
- A special planar satisfiability problem and a consequence of its NP- completeness
- \(2K_{2}\) vertex-set partition into nonempty parts
- Vertex ranking of asteroidal triple-free graphs
- Boxicity and maximum degree
- Rainbow connection number and connected dominating sets
- \(P_{5}\)-free augmenting graphs and the maximum stable set problem
- Dominating cliques in graphs
- Enumeration of difference graphs
- Boxicity of Halin graphs
- Boxicity of circular arc graphs
- Ranking chain sum orders
- Cubicity, degeneracy, and crossing number
- Minors and dimension
- The complexity of facets (and some facets of complexity)
- On the structure of (\(P_{5}\),\,gem)-free graphs
- A characterization of the \(n\)-agent Pareto dominance relation
- Minimal fill in O(\(n^{2.69}\)) time
- Sublinear approximation algorithms for boxicity and related problems
- Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width
- Some results on maximum stable sets in certain \(P_{5}\)-free graphs
- Graph classes with structured neighborhoods and algorithmic applications
- Reasoning about visibility
- On the cubicity of bipartite graphs
- Boxicity and cubicity of asteroidal triple free graphs
- Algorithmic aspects of intersection graphs and representation hypergraphs
- Steiner transitive-closure spanners of low-dimensional posets
- Steiner transitive-closure spanners of low-dimensional posets
- Alternation graphs
- On the cubicity of certain graphs
- Dimension preserving contractions and a finite list of 3-irreducible posets
- Geometric representation of graphs in low dimension using axis parallel boxes
- Transitive closure for restricted classes of partial orders
- Multidimensional scaling and threshold graphs
- NP-completeness properties about linear extensions
- Induced matchings in asteroidal triple-free graphs
- On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
- Transitive-closure spanners: a survey
- Matchings, coverings, and Castelnuovo-Mumford regularity
- Lower bounds for boxicity
- On variations of \(P_{4}\)-sparse graphs
- On dynamic threshold graphs and related classes
- (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
- Boxicity and treewidth
- Partially ordered knapsack and applications to scheduling
- The cubicity of hypercube graphs
- \(H\)-product of graphs, \(H\)-threshold graphs and threshold-width of graphs
- New constructions for provably-secure time-bound hierarchical key assignment schemes
- Split dimension of graphs
- Convexity in partial cubes: the hull number
- Representing graphs as the intersection of cographs and threshold graphs
- Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications
- Counting and enumerating independent sets with applications to combinatorial optimization problems
- On treewidth and minimum fill-in of asteroidal triple-free graphs
- Geometrical embeddings of graphs
- Planar graphs and poset dimension
- On realizable biorders and the biorder dimension of a relation
- Boxicity of line graphs
- Paretian partial orders: the two-agent case
- Hereditary efficiently dominatable graphs
- On the generation of circuits and minimal forbidden sets
- The order dimension of the poset of regions in a hyperplane arrangement.
- The Dilworth number of auto-chordal bipartite graphs
- The complexity of embedding orders into small products of chains
- On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size
- On the vertex ranking problem for trapezoid, circular-arc and other graphs
- Graphs with the fewest matchings
- Succinct posets
- The computational complexity of rationalizing Pareto optimal choice behavior
- On maximal chain subgraphs and covers of bipartite graphs
- Cubicity, boxicity, and vertex cover
- Localized and compact data-structure for comparability graphs
- Threshold Dimension of Graphs
- An \(O(n^3)\) time algorithm for recognizing threshold dimension 2 graphs
- Fractional dimension of partial orders
- Vertex ranking of asteroidal triple-free graphs
- Point algebras for temporal reasoning: Algorithms and complexity
- Large Induced Subgraphs via Triangulations and CMSO
- Semi-transitive orientations and word-representable graphs
- Cubicity of interval graphs and the claw number
- Cubicity of interval graphs and the claw number
- Timestamping messages and events in a distributed system using synchronous communication
- Asymptotic enumeration of two-dimensional posets
- Cubicity and bandwidth
- The complexity of the defensive domination problem in special graph classes
- Soft dimension theory.
- Searching for the dimension of valued preference relations.
- On \(H\)-topological intersection graphs
- Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity
- The interval inclusion number of a partially ordered set
- Algorithmic Aspects of Quasi-Total Roman Domination in Graphs
- Ray shooting from convex ranges
- Optimal shooting: Characterizations and applications
- The complexity of the partial order dimension problem: closing the gap
- \(N\)-free orders and minimal interval extensions
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)
