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 (only showing first 100 items - show all)

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 ⋮ Vertex ranking of asteroidal triple-free 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 ⋮ Well-quasi-ordering and Embeddability of Relational Structures ⋮ 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 ⋮ Threshold graphs and synchronization protocols ⋮ Representing graphs as the intersection of cographs and threshold graphs ⋮ Fully Dynamically Maintaining Minimal Integral Separator for Threshold and Difference Graphs ⋮ Word-representability of graphs with respect to split recomposition ⋮ On multipartite posets ⋮ Unnamed Item ⋮ Embedding ordered sets into distributive lattices ⋮ Recognizing unit multiple interval graphs is hard ⋮ Intersection of chordal graphs and some related partition problems ⋮ 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 ⋮ 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

Cites Work

This page was built for publication: The Complexity of the Partial Order Dimension Problem