Cyclic ordering is NP-complete

DOI10.1016/0304-3975(77)90005-6zbMath0383.68045MaRDI QIDQ1248373

Nimrod Megiddo, Zvi Galil

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

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

06A05: Total orders

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

• Partial and complete cyclic orders
• The complexity of theorem-proving procedures
• Unnamed Item