For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Graph Theoretic Problems Complete for Nondeterministic Log-Space
Yoshiaki FUKAZAWA Shigeki IWATA
IEICE TRANSACTIONS (1976-1990)
Publication Date: 1983/02/25
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Computational Complexity
Full Text: PDF(466.4KB)>>
Some graph theoretic problems are considered and these problems are proved to be complete for nondeterministic log-space. These graph problems concern matching, connectivity, feedback node set, diameter, radius and so on. A consideration is also mode in connection with the Jones' open problem.