The Complexity of the Partial Order Dimension Problem
From MaRDI portal
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)- A graph theoretic approach to solve special knapsack problems in polynomial time
- Certifying fully dynamic algorithms for recognition and Hamiltonicity of threshold and chain graphs
- The fixed point property for ordered sets of interval dimension 2
- Localized and compact data-structure for comparability graphs
- Recognizing unit multiple intervals is hard
- Steiner transitive-closure spanners of low-dimensional posets
- Matchings, coverings, and Castelnuovo-Mumford regularity
- NP-completeness properties about linear extensions
- Tree pivot-minors and linear rank-width
- On dynamic threshold graphs and related classes
- Steiner transitive-closure spanners of low-dimensional posets
- On the vertex ranking problem for trapezoid, circular-arc and other graphs
- Strict 2-threshold graphs
- New constructions for provably-secure time-bound hierarchical key assignment schemes
- Finite dimensional scattered posets
- \(k\)-majority digraphs and the hardness of voting with a constant number of voters
- Dimension invariance of subdivisions
- Ray shooting from convex ranges
- Boxicity of Halin graphs
- Soft dimension theory.
- Searching for the dimension of valued preference relations.
- Threshold graphs and synchronization protocols
- 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
- Boxicity of circular arc graphs
- Reasoning about visibility
- Sublinear approximation algorithms for boxicity and related problems
- On variations of \(P_{4}\)-sparse graphs
- Counting and enumerating independent sets with applications to combinatorial optimization problems
- A characterization of the n-agent Pareto dominance relation
- Minimal fill in O(\(n^{2.69}\)) time
- Geometric representation of graphs in low dimension using axis parallel boxes
- The Hardness of Approximating Poset Dimension
- Powers of geometric intersection graphs and dispersion algorithms
- On treewidth and minimum fill-in of asteroidal triple-free graphs
- Intersection representation of digraphs in trees with few leaves
- 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
- The computational complexity of rationalizing Pareto optimal choice behavior
- On the complexity of the k-chain subgraph cover problem
- Planar graphs and poset dimension
- The order dimension of the poset of regions in a hyperplane arrangement.
- Graph classes and forbidden patterns on three vertices
- On bipartite graphs with the minimum number of spanning trees
- On \(H\)-topological intersection graphs
- Comparability graphs and intersection graphs
- FO model checking on geometric graphs
- Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity
- Split dimension of graphs
- Cubicity, degeneracy, and crossing number
- Convexity in partial cubes: the hull number
- Fully dynamically maintaining minimal integral separator for threshold and difference graphs
- Ranking chain sum orders
- Bounding threshold dimension: realizing graphic Boolean functions as the AND of majority gates
- Embedding ordered sets into distributive lattices
- On the cubicity of bipartite graphs
- On the structure of (\(P_{5}\),\,gem)-free graphs
- An \(O(n^3)\) time algorithm for recognizing threshold dimension 2 graphs
- Vertex ranking of asteroidal triple-free graphs
- On edge transitivity of directed graphs
- On list \(k\)-coloring convex bipartite graphs
- Boxicity of line graphs
- Tight bounds to localize failure nodes on trees, grids and through embeddings under Boolean network tomography
- Role coloring bipartite graphs
- Some bounds on the threshold dimension of graphs
- The hardness of approximating the boxicity, cubicity and threshold dimension of a graph
- Vertex ranking of asteroidal triple-free graphs
- AN ALGORITHMIC APPROACH TO PREFERENCE REPRESENTATION
- Transitive-closure spanners: a survey
- Cubicity and bandwidth
- FO model checking of geometric graphs
- Dominance drawings for DAGs with bounded modular width
- On the Cubicity of Interval Graphs
- On the generation of circuits and minimal forbidden sets
- Bounds on Threshold Dimension and Disjoint Threshold Coverings
- Graph classes with structured neighborhoods and algorithmic applications
- Bounds for boxicity of circular clique graphs and zero-divisor graphs
- Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width
- On 4-Sachs optimal graphs
- Lower bounds for boxicity
- Geometrical embeddings of graphs
- The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial
- Decomposing weighted digraphs into sums of chains
- On finding the bidimension of a relation
- Trapezoid graphs and their coloring
- Dominating cliques in graphs
- Word-representability of graphs with respect to split recomposition
- Fast algorithms for computing the characteristic polynomial of threshold and chain graphs
- Transitive closure for restricted classes of partial orders
- The relationship between the threshold dimension of split graphs and various dimensional parameters
- On the interval completion of chordal graphs
- \(2K_{2}\) vertex-set partition into nonempty parts
- Asymptotic enumeration of two-dimensional posets
- The complexity of facets (and some facets of complexity)
- The complexity of the defensive domination problem in special graph classes
- The lexicographic method for the threshold cover problem
- Multidimensional scaling and threshold 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)
