https://acawiki.org/api.php?action=feedcontributions&feedformat=atom&user=JfinkelsAcaWiki - User contributions [en]2026-06-09T23:07:14ZUser contributionsMediaWiki 1.31.12https://acawiki.org/index.php?title=Total_ordering_problem&diff=4249Total ordering problem2010-10-04T18:18:47Z<p>Jfinkels: added the total ordering problem</p>
<hr />
<div>{{Summary<br />
|title=Total Ordering Problem<br />
|authors=J. Opatrný<br />
|tags=complexity, np-complete, computational complexity<br />
|summary=Proves the NP-completeness of the total ordering problem: given finite sets S and R, where R is a subset of S x S x S, does there exist a total ordering of the elements of S such that for all (x, y, z) in R, either x < y < z or z < y < x? The reduction is from the hypergraph 2-colorability problem with edges of size at most 3.<br />
<br />
This problem is in "Computers and Intractibility" by Garey and Johnson as problem MS1, the betweenness problem.<br />
|journal=SIAM Journal on Computing<br />
|pub_date=1979<br />
|doi=10.1137/0208008<br />
|subject=Computer Science<br />
}}</div>Jfinkels