Combinatorial Algorithms Using Boolean Processing

スポンサーリンク

概要

• 論文の詳細を見る

• The backtracking technique has been used to solve various problems of generating all combinatorial objects. A feature of this technique is that the conditions attached to the problem and the search for solutions are closely related. Thus, in order to obtain all solutions fficiently, it is necessary to discover suitable data structures for each problem. In this paper, we propose a new general technique for solving combinatorial problems by describing the conditions and searching for solutions separately. First, we describe the conditions attached to the problem by using Boolean functoins. Next, we construct a binary decision diagram (BDD), representing Boolean functions by using an efficient BDD manipulator. Finally, we traverse the BDD and obtain all the solutions. By applying this technique to many combinatorial problems, we have discovered that the conditions attached to a problem can be briefly described by Boolean functions, and that all the solutions can be obtained effciently.

• 一般社団法人情報処理学会の論文
• 1994-09-15

著者

• Yajima Shuzo

  Department Of Information Science Kyoto University

• Semba Ichiro

  College Of General Education Ibaraki University

• Yajima Shuzo

  Department Of Information Science Facu1ty Of Engineering Kyoto University

関連論文

• A Computer Communication Control Technique for Virtualization of Network Memory Resources and Its Implementation
• Regular Temporal Logic Expressively Equivalent to Finite Automata and Its Application to Logic Design Verification
• Locally Exhaustive Testing of Combinational Circuits Using Linear Logic Circuits
• Minimum One-Shot State Assignment for Asynchronous Sequential Machines Using BDD
• The Complexity of the Optimal Variable Ordering Problems of a Shared Binary Decision Diagram
• A Raster-scan Computer Graphic Display Device Having Random-scan Functions with Color Specifying Light Pen Facility
• On the Preprocessing Algorithm Used in the Boyer-Moore Algorithm for String Searching
• Combinatorial Algorithms Using Boolean Processing
• Minimum Single Transition-Time Assignments for Asynchronous Sequential Circuits Using BDD
• An Algorithm for Division of Large Integers

スポンサーリンク