Presentation	1995/7/27 An approach to acquisition of natural evidence for some graph problems Koichi Yamazaki,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	An algorithm D is a decision algorithm if D decide whether a problem has a explanation or not (D outputs "yes" or "no"). An algorithm S is a search algorithm if S find a explanation for a problem (when the problem has a explanation). A explanation is called a natural evidence. We consider the following three graph problems : k-COLORABILITY, k-BANDWIDTH, and k-UNIFORM EMULATION ON A PATH. In this paper, we discuss the efficiency of finding a natural evidence for the graph problems when its search algorithm can employ its decision algorithm as oracle. We will show that for each the three problem if the decision problem is solvable in time D(n) then the corresponding search problem is solvable in O(n^2×D(n)) time.
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)	k-COLORABILITY / k-BANDWIDTH / decision problem / search problem / critical graph
Paper #
Date of Issue

Conference Information
Committee	COMP
Conference Date	1995/7/27(1days)
Place (in Japanese)	(See Japanese page)
Place (in English)
Topics (in Japanese)	(See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To	Theoretical Foundations of Computing (COMP)
Language	ENG
Title (in Japanese)	(See Japanese page)
Sub Title (in Japanese)	(See Japanese page)
Title (in English)	An approach to acquisition of natural evidence for some graph problems
Sub Title (in English)
Keyword(1)	k-COLORABILITY
Keyword(2)	k-BANDWIDTH
Keyword(3)	decision problem
Keyword(4)	search problem
Keyword(5)	critical graph
1st Author's Name	Koichi Yamazaki
1st Author's Affiliation	University of Electro-Communications()
Date	1995/7/27
Paper #
Volume (vol)	vol.95
Number (no)	188
Page	pp.pp.-
#Pages	6
Date of Issue