Golumbic, Martin Charles; Shamir, Ron Complexity and algorithms for reasoning about time: A graph-theoretic approach. (English) Zbl 0795.68095 J. Assoc. Comput. Mach. 40, No. 5, 1108-1133 (1993). Cited in 1 ReviewCited in 47 Documents MSC: 68Q25 Analysis of algorithms and problem complexity 68T15 Theorem proving (deduction, resolution, etc.) (MSC2010) 68R10 Graph theory (including graph drawing) in computer science 92D20 Protein sequences, DNA sequences Keywords:complexity; DNA mapping; temporal reasoning; interval algebras; interval orders; interval graphs; satisfiability; sandwich problem; NP-complete PDFBibTeX XMLCite \textit{M. C. Golumbic} and \textit{R. Shamir}, J. Assoc. Comput. Mach. 40, No. 5, 1108--1133 (1993; Zbl 0795.68095) Full Text: DOI