The complexity of problems concerning graphs with regularities

1. Bentley, J.L., Ottmann, T., The complexity of manipulating hierarchically defined sets of rectangles, MFCS 1981, in Lecture Notes in Computer Science 118, 1–15.

   Google Scholar 

2. Garey, M.R., Johnson, D.S., Computers and Intractability, A Guide to the Theory of NP-Completeness, W.H. Freeman and Co., San Francisco 1979.

   Google Scholar 

3. Jones, N.D., Lien, Y.E., Laaser, W.T., New problems complete for nondeterministic log space, Mathematical Systems Theory 10(1976), 1–17.

   Google Scholar 

4. Jones, N.D., Space-bounded reducibility among combinatorial problems, Journal of Computer and System Sciences 11(1975), 68–85.

   Google Scholar 

5. Meyer, A.R., Stockmeyer, L.J., The equivalence problem for regular expressions with squaring requires exponential space, Proc. of the 13th SWAT (1972), 125–129.

   Google Scholar 

6. Stockmeyer, L.J., Meyer, A.R., Word problems requiring exponential time, Proc. of the 5th STOC(1973), 1–9.

   Google Scholar 

7. Stockmeyer, L.J., The polynomial-time hierarchy, Theoretical Computer Science 3(1977), 1–22.

   Google Scholar 

8. Sudborough, I.H., On tape-bounded complexity classes and multihead finite automata, Journal of Computer and System Sciences 10(1975), 62–76.

   Google Scholar 

9. Wagner, K., Compact descriptions and the counting polynomial-time hierarchy (extended abstract), to appear in the Proc. of the 2nd Frege Conf., Schwerin 1984.

   Google Scholar 

10. Wagner, K., The counting polynomial-time hierarchy, preprint.

    Google Scholar 

11. Wagner, K., The complexity of combinatorial problems with compactly described instances, preprint.

    Google Scholar 

Download references