Journal of the ACM Bibliography
Martin Charles Golumbic
and Ron Shamir. Complexity
and algorithms for reasoning about time: A graph-theoretic approach.
Journal of the ACM, 40(5):1108-1133, November 1993.
[BibTeX entry]
Selected papers that cite this one
- Martin Charles Golumbic, Haim Kaplan, and Ron Shamir. Graph sandwich
problems. Journal of Algorithms, 19(3):449-473,
November 1995.
- Haim Kaplan and Ron Shamir. Pathwidth,
bandwidth, and completion problems to proper interval graphs with small
cliques. SIAM Journal on Computing, 25(3):540-561, June
1996.
- Paul E. Kearney and Derek G. Corneil. Tree powers.
Journal of Algorithms, 29(1):111-131, October 1998.
- Ron van der Meyden. The complexity of
querying indefinite data about linearly ordered domains.
Journal of Computer and System Sciences, 54(1):113-135,
February 1997.
- Bernhard Nebel and Hans-Jürgen Bürckert. Reasoning about temporal relations: A
maximal tractable subclass of Allen's interval algebra.
Journal of the ACM, 42(1):43-66, January 1995.
- Itsik Pe'er and Ron Shamir. Satisfiability problems on
intervals and unit intervals. Theoretical Computer
Science, 175(2):349-372, 10 April 1997.
Selected references
- Graham Brightwell and Peter Winkler. Counting linear
extensions is #P-complete. In Proceedings of the Twenty Third
Annual ACM Symposium on Theory of Computing, pages 175-181, New
Orleans, Louisiana, 6-8 May 1991.
- Csaba P. Gabor, Kenneth J. Supowit, and Wen-Lian Hsu. Recognizing circle graphs in
polynomial time. Journal of the ACM, 36(3):435-473,
July 1989.
- Thomas J. Schaefer. The complexity of
satisfiability problems. In Conference Record of the Tenth
Annual ACM Symposium on Theory of Computing, pages 216-226, San
Diego, California, 1-3 May 1978.
Shortcuts: