Cyclic ordering is NP-complete
From MaRDI portal
Publication:1248373
DOI10.1016/0304-3975(77)90005-6zbMath0383.68045MaRDI QIDQ1248373
Publication date: 1978
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(77)90005-6
Related Items
Unnamed Item, Axiomatic scale theory, Simultaneous Embedding, Cyclic Extensions of Order Varieties, Extending partial representations of circular-arc graphs, Vincular pattern avoidance on cyclic permutations, Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables, Linear kernel for \textsc{Rooted Triplet Inconsistency} and other problems based on conflict packing technique, Satisfying ternary permutation constraints by multiple linear orders or phylogenetic trees, A mixed integer linear programming formulation of the maximum betweenness problem, Polyhedral structure and properties of a model for layout design, A new approach to cyclic ordering of 2D orientations using ternary relation algebras, On the weighted quartet consensus problem, Extensions of partial cyclic orders, Euler numbers and multidimensional boustrophedons, A priori TSP in the scenario model, Describing hereditary properties by forbidden circular orderings, A new approach for identifying the Kemeny median ranking, A priori TSP in the Scenario Model, On Random Ordering Constraints
Cites Work