Graph Theoretic Problems Complete for Nondeterministic Log-Space

Yoshiaki FUKAZAWA  Shigeki IWATA  

Publication
IEICE TRANSACTIONS (1976-1990)   Vol.E66   No.2   pp.102-107
Publication Date: 1983/02/25
Online ISSN: 
DOI: 
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Computational Complexity
Keyword: 


Full Text: PDF(466.4KB)>>
Buy this Article




Summary: 
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.