Δ ^p₂ -complete lexicographically first maximal subgraph problems

1. Anderson, R. and Mayr, E.W., Parallelism and the maximal path problem, Inf. Process. Lett. 24 (1987) 121–124.

   Google Scholar 

2. Berge, C., Graphes et hypergraphes, Dunod, 1970.

   Google Scholar 

3. Garey, M.R., Johnson, D.S. and Tarjan, R.E., The planar Hamiltonian circuit problem is NP-complete, SIAM J. Comput. 5 (1976) 704–714.

   Google Scholar 

4. Goldschlager, L.M., The monotone and planar circuit value problems are log space complete for P, SIGACT News 9 (1977) 25–29.

   Google Scholar 

5. Lewis, J.M. and Yannakakis, M., The node deletion problems for hereditary properties is NP-complete, J. Comput. System Sci. 20 (1980) 219–230.

   Google Scholar 

6. Martel, C.U., Lower bounds on parallel algorithms for finding the first maximal independent set, Inf. Process. Lett. 22 (1986) 81–85.

   Google Scholar 

7. Miyano, S., The lexicographically first maximal subgraph problems: P-completeness and NC algorithms, Proc. 14th ICALP (LNCS 267)(1987) 425–434.

   Google Scholar 

8. Miyano, S., A parallelizable lexicographically first maximal edge-induced subgraph problem, Inf. Process. Lett. 29 (1988) 75–78.

   Google Scholar 

9. Papadimitriou, C.H., On the complexity of unique solution, J. Assoc. Comput. Mach. 31 (1984) 392–400.

   Google Scholar 

10. Wagner, K.W., More complicated questions about maxima and minima, and some closure of NP, Proc. 13th ICALP (LNCS 226)(1986) 434–443.

    Google Scholar 

11. Yannakakis, M., The effect of a connectivity requirement on the complexity of maximum subgraph problems, J. Assoc. Comput. Mach. 26 (1979) 618–630.

    Google Scholar 

12. Yannakakis, M., Node-deletion problems on bipartite graphs, SIAM J. Comput. 10 (1981) 310–327.

    Google Scholar 

Download references