The Complexity of the Partial Order Dimension Problem

Cites Work

Cited In (only showing first 100 items - show all)

Localized and compact data-structure for comparability graphs
Steiner transitive-closure spanners of low-dimensional posets
NP-completeness properties about linear extensions
Matchings, coverings, and Castelnuovo-Mumford regularity
On dynamic threshold graphs and related classes
On the vertex ranking problem for trapezoid, circular-arc and other graphs
Alternation Graphs
New constructions for provably-secure time-bound hierarchical key assignment schemes
Boxicity of Halin graphs
Boxicity of circular arc graphs
Sublinear approximation algorithms for boxicity and related problems
Reasoning about visibility
On variations of \(P_{4}\)-sparse graphs
Counting and enumerating independent sets with applications to combinatorial optimization problems
The Hardness of Approximating Poset Dimension
On Maximal Chain Subgraphs and Covers of Bipartite Graphs
Minimal fill in O(\(n^{2.69}\)) time
A characterization of the \(n\)-agent Pareto dominance relation
Geometric representation of graphs in low dimension using axis parallel boxes
On treewidth and minimum fill-in of asteroidal triple-free graphs
Dimension-2 poset competition numbers and dimension-2 poset double competition numbers
Boxicity and cubicity of asteroidal triple free graphs
The cubicity of hypercube graphs
Planar graphs and poset dimension
The computational complexity of rationalizing Pareto optimal choice behavior
Comparability graphs and intersection graphs
Cubicity, degeneracy, and crossing number
Split dimension of graphs
Convexity in partial cubes: the hull number
Structural parameterizations for boxicity
Ranking chain sum orders
On the structure of (\(P_{5}\),\,gem)-free graphs
On the cubicity of bipartite graphs
An \(O(n^3)\) time algorithm for recognizing threshold dimension 2 graphs
Vertex ranking of asteroidal triple-free graphs
Vertex ranking of asteroidal triple-free graphs
Boxicity of line graphs
The hardness of approximating the boxicity, cubicity and threshold dimension of a graph
On the generation of circuits and minimal forbidden sets
Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width
Graph classes with structured neighborhoods and algorithmic applications
Lower bounds for boxicity
Geometrical embeddings of graphs
Rainbow connections of graphs: a survey
Dominating cliques in graphs
Trapezoid graphs and their coloring
Hereditary Efficiently Dominatable Graphs
Transitive closure for restricted classes of partial orders
\(2K_{2}\) vertex-set partition into nonempty parts
The complexity of facets (and some facets of complexity)
Multidimensional scaling and threshold graphs
Succinct posets
A special planar satisfiability problem and a consequence of its NP- completeness
On realizable biorders and the biorder dimension of a relation
Induced matchings in asteroidal triple-free graphs
On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
(\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
The complexity of embedding orders into small products of chains
Semi-transitive orientations and word-representable graphs
Boxicity and maximum degree
Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications
Steiner Transitive-Closure Spanners of Low-Dimensional Posets
Fractional dimension of partial orders
Rainbow connection number and connected dominating sets
Minors and dimension
Paretian partial orders: the two-agent case
A recognition algorithm for orders of interval dimension two
Representing graphs as the intersection of cographs and threshold graphs
\(P_{5}\)-free augmenting graphs and the maximum stable set problem
Algorithmic aspects of intersection graphs and representation hypergraphs
Partially ordered knapsack and applications to scheduling
Enumeration of difference graphs
Dimension preserving contractions and a finite list of 3-irreducible posets
The Dilworth number of auto-chordal bipartite graphs
On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size
Cubicity, boxicity, and vertex cover
Point algebras for temporal reasoning: Algorithms and complexity
Large Induced Subgraphs via Triangulations and CMSO
Boxicity and treewidth
On the cubicity of certain graphs
Some results on maximum stable sets in certain \(P_{5}\)-free graphs
Transitive-Closure Spanners: A Survey
\(H\)-product of graphs, \(H\)-threshold graphs and threshold-width of graphs
Threshold Dimension of Graphs
The fixed point property for ordered sets of interval dimension 2
Ray shooting from convex ranges
Strict 2-threshold graphs
Finite dimensional scattered posets
\(k\)-majority digraphs and the hardness of voting with a constant number of voters
Dimension invariance of subdivisions
Threshold graphs and synchronization protocols
Soft dimension theory.
Searching for the dimension of valued preference relations.
Computing the dimension of N-free ordered sets is NP-complete
Dimension of valued relations
On bipartite graphs having minimum fourth adjacency coefficient
On the complexity of the black-and-white coloring problem on some classes of perfect graphs
Intersection representation of digraphs in trees with few leaves
Powers of geometric intersection graphs and dispersion algorithms
On \(H\)-topological intersection graphs

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)