The Complexity of the Partial Order Dimension Problem

DOI10.1137/0603036zbMath0516.06001OpenAlexW2047899424MaRDI QIDQ3663349

Publication date: 1982

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0603036

zbMATH Keywords

NP- completeness dimension of partial order intersection of linear orders

Mathematics Subject Classification ID

Partial orders, general (06A06) Coloring of graphs and hypergraphs (05C15)

Related Items

Minimal fill in O(\(n^{2.69}\)) time, Some complexity results about threshold graphs, A special planar satisfiability problem and a consequence of its NP- completeness, Decomposing weighted digraphs into sums of chains, A characterization of the \(n\)-agent Pareto dominance relation, On some complexity properties of N-free posets and posets with bounded decomposition diameter, Structural parameterizations for boxicity, Ranking chain sum orders, An \(O(n^3)\) time algorithm for recognizing threshold dimension 2 graphs, Vertex ranking of asteroidal triple-free graphs, FO model checking on geometric graphs, A recognition algorithm for orders of interval dimension two, Enumeration of difference graphs, On edge transitivity of directed graphs, On finding the bidimension of a relation, Geometric representation of graphs in low dimension using axis parallel boxes, Succinct posets, Multidimensional scaling and threshold graphs, Minors and dimension, 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, The hardness of approximating the boxicity, cubicity and threshold dimension of a graph, The complexity of embedding orders into small products of chains, Partially ordered knapsack and applications to scheduling, \(H\)-product of graphs, \(H\)-threshold graphs and threshold-width of graphs, Graph classes with structured neighborhoods and algorithmic applications, On treewidth and minimum fill-in of asteroidal triple-free graphs, Steiner transitive-closure spanners of low-dimensional posets, Matchings, coverings, and Castelnuovo-Mumford regularity, Co-bipartite neighborhood edge elimination orderings, Boxicity of line graphs, Soft dimension theory., Sublinear approximation algorithms for boxicity and related problems, Searching for the dimension of valued preference relations., Convexity in partial cubes: the hull number, Forbidden substructure for interval digraphs/bigraphs, Reasoning about visibility, On variations of \(P_{4}\)-sparse graphs, Semi-transitive orientations and word-representable graphs, On dynamic threshold graphs and related classes, 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, One-sided weak dominance drawing, The order dimension of the poset of regions in a hyperplane arrangement., On the order dimension of outerplanar maps, (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization., Comparability graphs and intersection graphs, An appraisal of computational complexity for operations researchers, Boxicity of circular arc graphs, The interval inclusion number of a partially ordered set, Split dimension of graphs, The computational complexity of rationalizing Pareto optimal choice behavior, Transitive closure for restricted classes of partial orders, The Dilworth number of auto-chordal bipartite graphs, On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size, Recognizing strict 2-threshold graphs in O(m) time, An \(O(n^ 3)\) recognition algorithm for bithreshold graphs, New constructions for provably-secure time-bound hierarchical key assignment schemes, Graphs with the fewest matchings, Bipartite bithreshold graphs, Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications, \(N\)-free orders and minimal interval extensions, \(2K_{2}\) vertex-set partition into nonempty parts, Dimension-2 poset competition numbers and dimension-2 poset double competition numbers, Boxicity and cubicity of asteroidal triple free graphs, 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, On the cubicity of bipartite graphs, NP-completeness properties about linear extensions, The cubicity of hypercube graphs, Fractional dimension of partial orders, A constant factor approximation algorithm for boxicity of circular arc graphs, 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 complexity of the k-chain subgraph cover problem, Computing the dimension of N-free ordered sets is NP-complete, Dimension preserving contractions and a finite list of 3-irreducible posets, Geometrical embeddings of graphs, On the stab number of rectangle intersection graphs, On the cubicity of certain graphs, On the cubicity of interval graphs, Counting and enumerating independent sets with applications to combinatorial optimization problems, Dimension of valued relations, On realizable biorders and the biorder dimension of a relation, Interval graphs and related topics, The complexity of facets (and some facets of complexity), On the greedy dimension of a partial order, The relationship between the threshold dimension of split graphs and various dimensional parameters, Drawing orders with few slopes, Point algebras for temporal reasoning: Algorithms and complexity, Tight bounds to localize failure nodes on trees, grids and through embeddings under Boolean network tomography, Rainbow connection number and connected dominating sets, Boxicity and treewidth, Threshold Dimension of Graphs, On the geometric separability of Boolean functions, Hereditary Efficiently Dominatable Graphs, The fixed point property for ordered sets of interval dimension 2, Recognizing simple-triangle graphs by restricted 2-chain subgraph cover, Chronological rectangle digraphs which are two-terminal series-parallel, Bounding threshold dimension: realizing graphic Boolean functions as the AND of majority gates, Large Induced Subgraphs via Triangulations and CMSO, On the Cubicity of Interval Graphs, The Hardness of Approximating Poset Dimension, Cubicity and bandwidth, Rainbow connections of graphs: a survey, The Complexity of the Partial Order Dimension Problem: Closing the Gap, On 4-Sachs optimal graphs, Dominance drawings for DAGs with bounded modular width, Certifying fully dynamic algorithms for recognition and Hamiltonicity of threshold and chain graphs, Finite dimensional scattered posets, Timestamping messages and events in a distributed system using synchronous communication, Intersection representation of digraphs in trees with few leaves, On the vertex ranking problem for trapezoid, circular-arc and other graphs, On the complexity of the black-and-white coloring problem on some classes of perfect graphs, Dimension invariance of subdivisions, Dominating cliques in graphs, Secure Authenticated Comparisons, Optimal shooting: Characterizations and applications, Steiner Transitive-Closure Spanners of Low-Dimensional Posets, Boxicity and maximum degree, Algorithmic Aspects of Quasi-Total Roman Domination in Graphs, Ray shooting from convex ranges, Bounds on Threshold Dimension and Disjoint Threshold Coverings, The lexicographic method for the threshold cover problem, Dominating cliques in graphs, On the interval completion of chordal graphs, Transitive-Closure Spanners: A Survey, Happy set problem on subclasses of co-comparability graphs, AN ALGORITHMIC APPROACH TO PREFERENCE REPRESENTATION, A Graph Theoretic Approach to Solve Special Knapsack Problems in Polynomial Time, The complexity of the defensive domination problem in special graph classes, Cubicity of interval graphs and the claw number, Cubicity, degeneracy, and crossing number, On \(H\)-topological intersection graphs, Deciding the Bell Number for Hereditary Graph Properties, Representing graphs as the intersection of cographs and threshold graphs, Fully Dynamically Maintaining Minimal Integral Separator for Threshold and Difference Graphs, On multipartite posets, Unnamed Item, Embedding ordered sets into distributive lattices, On Maximal Chain Subgraphs and Covers of Bipartite Graphs, On list \(k\)-coloring convex bipartite graphs, On minimal forbidden subgraph characterizations of balanced graphs, \(k\)-majority digraphs and the hardness of voting with a constant number of voters, Alternation Graphs, Crisp dimension theory and valued preference relations, On the Cubicity of AT-Free Graphs and Circular-Arc Graphs, Role coloring bipartite graphs, The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial, Cubicity of Interval Graphs and the Claw Number, Fast algorithms for computing the characteristic polynomial of threshold and chain graphs, Graph Classes and Forbidden Patterns on Three Vertices, Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity, Lower bounds for boxicity, Paretian partial orders: the two-agent case, Tree Pivot-Minors and Linear Rank-Width, MINING POSETS FROM LINEAR ORDERS, On bipartite graphs having minimum fourth adjacency coefficient

Cites Work