Cyclic ordering is NP-complete

DOI10.1016/0304-3975(77)90005-6zbMath0383.68045OpenAlexW2132421209MaRDI 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

Analysis of algorithms and problem complexity (68Q25) Total orders (06A05)

Related Items

Polyhedral structure and properties of a model for layout design, Extending partial representations of circular-arc graphs, 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, Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables, Vincular pattern avoidance on cyclic permutations, A priori TSP in the Scenario Model, On the weighted quartet consensus problem, Extensions of partial cyclic orders, Euler numbers and multidimensional boustrophedons, Cyclic Extensions of Order Varieties, A mixed integer linear programming formulation of the maximum betweenness problem, Unnamed Item, A priori TSP in the scenario model, On Random Ordering Constraints, Axiomatic scale theory, Simultaneous Embedding, A new approach to cyclic ordering of 2D orientations using ternary relation algebras, A new approach for identifying the Kemeny median ranking, Describing hereditary properties by forbidden circular orderings

Cites Work

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