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.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Yoshiaki FUKAZAWA, Shigeki IWATA, "Graph Theoretic Problems Complete for Nondeterministic Log-Space" in IEICE TRANSACTIONS on transactions,
vol. E66-E, no. 2, pp. 102-107, February 1983, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/transactions/10.1587/e66-e_2_102/_p
Copy
@ARTICLE{e66-e_2_102,
author={Yoshiaki FUKAZAWA, Shigeki IWATA, },
journal={IEICE TRANSACTIONS on transactions},
title={Graph Theoretic Problems Complete for Nondeterministic Log-Space},
year={1983},
volume={E66-E},
number={2},
pages={102-107},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={February},}
Copy
TY - JOUR
TI - Graph Theoretic Problems Complete for Nondeterministic Log-Space
T2 - IEICE TRANSACTIONS on transactions
SP - 102
EP - 107
AU - Yoshiaki FUKAZAWA
AU - Shigeki IWATA
PY - 1983
DO -
JO - IEICE TRANSACTIONS on transactions
SN -
VL - E66-E
IS - 2
JA - IEICE TRANSACTIONS on transactions
Y1 - February 1983
AB - 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.
ER -