Search for Author All Reviews
	Watanabe, Osamu     Options: All Media Types Journals Proceedings Div Books Whole Books Other Date Reviewed Title Author Publisher Published Date Descending Ascending Date Reviewed     1 - 5 of 6 reviews       Scale free interval graphs Miyoshi N., Shigezumi T., Uehara R., Watanabe O. Theoretical Computer Science 410(45): 4588-4600, 2009.  Type: Article Generating realistic graphs is a very important tool, since this process can lead to synthetic graphs with properties that characterize real-life networks. Therefore, synthetically generated graphs can be used in performance evaluation...... Jan 29 2010     Substring search and repeat search using factor oracles Kato R., Watanabe O. Information Processing Letters 93(6): 269-274, 2005.  Type: Article The authors of this paper, in the area of text searching, propose the use of factor oracles for searching substrings in a string. A factor oracle is a deterministic acyclic automaton. It can be used to index a document. An indexed docu...... Aug 16 2005     New collapse consequences of NP having small circuits Köbler J., Watanabe O. SIAM Journal on Computing 28(1): 311-324, 1998.  Type: Article A major question in complexity theory is whether sparse sets can beNP-hard. This question can be studied with respect to various notions ofhardness. The two most common such notions are polynomial-time many-onereductions and polynomial...... Jun 1 1999     Instance complexity Orponen P., Ko K., Schöning U., Watanabe O. Journal of the ACM 41(1): 96-121, 1994.  Type: Article What is a hard instance of a computational problem? This paper formalizes the intuitive idea that problems are hard if and only if they have infinitely many intrinsically hard instances. The authors introduce i c t ...... Dec 1 1994     Polynomial-time 1-Turing reductions from #PH to #P Toda S., Watanabe O. Theoretical Computer Science 100(1): 205-221, 1992.  Type: Article Various classes of languages and functions related to the polynomial-time hierarchy and relations between them, as well as certain reducibility relations lying between polynomial-time m - and Turing reducibility, are...... Jul 1 1993     Display 510152550100 per column
	Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud® Terms of Use | Privacy Policy