Polynomial Time Algorithm Solving the Refutation Tree Problem for Formal Graph Systems
スポンサーリンク
概要
- 論文の詳細を見る
The refutation tree problem for a formal graph system (FGS) is to compute a refutation tree which represents the logical structure of a graph generated by the FGS. We present three subclasses of FGSs: simple FGSs, size-bounded simple FGSs, and bounded simple FGSs. We give a polynomial-time algorithm solving the refutation tree problem for simple FGSs. For sizebounded simple FGSs generating undirected trees of constantly bounded valence, we show that a refutation tree of a graph definable by the FGS can be computed in NC^2. Moreover, we indicate that the refutation tree problem for bounded simple FGSs is in NC^2.
- Research Association of Statistical Sciencesの論文
- 1993-09-30
Research Association of Statistical Sciences | 論文
- CLUSTERING BY A FUZZY METRIC : APPLICATIONS TO THE CLUSTER-MEDIAN PROBLEM
- A FAMILY OF REGRESSION MODELS HAVING PARTIALLY ADDITIVE AND MULTIPLICATIVE COVARIATE STRUCTURE
- AN OPTIMAL STOPPING PROBLEM ON TREE
- ON THE ORDERS OF MAX-MIN FUNCTIONALS
- TREE EXPRESSIONS AND THEIR PRODUCT FORMULA