Cyclic ordering is NP-complete

The cyclic ordering problem is to recognize whether a collection of cyclically ordered triples of elements of a set T is derived from an arrangement of all the elements of T on a circle. This problem is shown to be NP-complete.

Authors

• Zvi Galil
• Nimrod Megiddo

Keywords

No keywords are indexed for this paper.