Total Ordering Problem
From MaRDI portal
Publication:4178507
DOI10.1137/0208008zbMath0395.68065OpenAlexW1964678328WikidataQ56486198 ScholiaQ56486198MaRDI QIDQ4178507
No author found.
Publication date: 1979
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0208008
Analysis of algorithms and problem complexity (68Q25) Applications of design theory to circuits and networks (94C30) Applications of graph theory to circuits and networks (94C15) Total orders (06A05) Discrete mathematics in relation to computer science (68R99)
Related Items
Permutation reconstruction from MinMax-betweenness constraints ⋮ Acyclicity in edge-colored graphs ⋮ The complexity of shelflisting ⋮ Permuting matrices to avoid forbidden submatrices ⋮ Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey ⋮ StreamTable: an area proportional visualization for tables with flowing streams ⋮ Hardness of fully dense problems ⋮ Expansion of gene clusters, circular orders, and the shortest Hamiltonian path problem ⋮ On the Generalised Character Compatibility Problem for Non-branching Character Trees ⋮ Sequence Covering Arrays and Linear Extensions ⋮ On the computational complexity of ordered subgraph recognition ⋮ Good orientations of unions of edge‐disjoint spanning trees ⋮ Unnamed Item ⋮ Upward book embeddability of \(st\)-graphs: complexity and algorithms ⋮ A geometric approach to betweenness ⋮ Simple linear time approximation algorithm for betweenness ⋮ Partial and simultaneous transitive orientations via modular decompositions ⋮ Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables ⋮ Characterization and representation problems for intersection betweennesses ⋮ Computing NodeTrix Representations of Clustered Graphs ⋮ Beyond Level Planarity ⋮ On Random Betweenness Constraints ⋮ On subbetweennesses of trees: hardness, algorithms, and characterizations ⋮ Algorithms and complexity of sandwich problems in graphs (extended abstract) ⋮ Unnamed Item ⋮ Strict betweennesses induced by posets as well as by graphs ⋮ Unnamed Item ⋮ Path-based supports for hypergraphs ⋮ Betweenness parameterized above tight lower bound ⋮ Upward Partitioned Book Embeddings ⋮ Crossing-constrained hierarchical drawings ⋮ On the complexity of computing treebreadth ⋮ On Reichenbach's causal betweenness ⋮ A mixed integer linear programming formulation of the maximum betweenness problem ⋮ Anonymous monotonic social welfare functions ⋮ Common intervals and permutation reconstruction from \textit{MinMax}-betweenness constraints ⋮ Unnamed Item ⋮ Beyond level planarity: cyclic, torus, and simultaneous level planarity ⋮ Inapproximability for metric embeddings into $\mathbb{R}^{d}$ ⋮ The importance of being proper ⋮ On the Hardness and Inapproximability of Recognizing Wheeler Graphs ⋮ Recognizing \(k\)-clique extendible orderings ⋮ Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems ⋮ Bounded Embeddings of Graphs in the Plane ⋮ On Random Ordering Constraints ⋮ Upward Book Embeddings of st-Graphs ⋮ Topological Birkhoff ⋮ Simultaneous Embedding ⋮ On recognizing staircase compatibility ⋮ Condorcet domains satisfying Arrow's single-peakedness ⋮ Advancements on SEFE and partitioned book embedding problems ⋮ On the complexity of recognizing Wheeler graphs
