Search Results:　 1-20 of 471

  • 1

    GPU Accelerated BCP Computation for SAT Algorithms  [in Japanese]

    Hironori Fujii , Noriyuki Fujimoto

    … 充足可能性判定問題 (SAT) は,応用範囲の広い最も基本的な NP 完全問題の一つである.SAT を解くためには最悪指数時間かかってしまうが,重要な問題なのでできるだけ高速に解きたいという要求がある.そこで我々は,GPU を用いて並列計算を行うことで,その計算時間を節約しようと考えた.本論文では,SAT アルゴリズムの主要な高速化手法のひとつである BCP ( Boolean Constraint Propagation) 処理を GPU を用いて並列化する手法を提案す …

    IPSJ SIG Notes 2011-HPC-132(27), 1-8, 2011-11-21

    CiNii Link1

  • 2

    GPU Accelerated BCP Computation for SAT Algorithms  [in Japanese]

    Hironori Fujii , Noriyuki Fujimoto

    … 充足可能性判定問題 (SAT) は,応用範囲の広い最も基本的な NP 完全問題の一つである.SAT を解くためには最悪指数時間かかってしまうが,重要な問題なのでできるだけ高速に解きたいという要求がある.そこで我々は,GPU を用いて並列計算を行うことで,その計算時間を節約しようと考えた.本論文では,SAT アルゴリズムの主要な高速化手法のひとつである BCP ( Boolean Constraint Propagation) 処理を GPU を用いて並列化する手法を提案す …

    IPSJ SIG Notes 2011-ARC-197(27), 1-8, 2011-11-21

    CiNii Link1

  • 3

    GPU Accelerated BCP Computation for SAT Algorithms  [in Japanese]

    Hironori Fujii , Noriyuki Fujimoto

    … 充足可能性判定問題 (SAT) は,応用範囲の広い最も基本的な NP 完全問題の一つである.SAT を解くためには最悪指数時間かかってしまうが,重要な問題なのでできるだけ高速に解きたいという要求がある.そこで我々は,GPU を用いて並列計算を行うことで,その計算時間を節約しようと考えた.本論文では,SAT アルゴリズムの主要な高速化手法のひとつである BCP ( Boolean Constraint Propagation) 処理を GPU を用いて並列化する手法を提案す …

    IPSJ SIG Notes 2011-HPC-132(27), 1-8, 2011-11-21

    CiNii Link1

  • 4

    GPU Accelerated BCP Computation for SAT Algorithms  [in Japanese]

    Hironori Fujii , Noriyuki Fujimoto

    … 充足可能性判定問題 (SAT) は,応用範囲の広い最も基本的な NP 完全問題の一つである.SAT を解くためには最悪指数時間かかってしまうが,重要な問題なのでできるだけ高速に解きたいという要求がある.そこで我々は,GPU を用いて並列計算を行うことで,その計算時間を節約しようと考えた.本論文では,SAT アルゴリズムの主要な高速化手法のひとつである BCP ( Boolean Constraint Propagation) 処理を GPU を用いて並列化する手法を提案す …

    IPSJ SIG Notes 2011-ARC-197(27), 1-8, 2011-11-21

    CiNii Link1

  • 5

    The Method That Reduce CNFSAT to HornSAT  [in Japanese]

    Koji Kobayashi

    … 完全問題であり,その充足可能性に関して項どうしが半順序構造を持つという優れた特長を持つ.そのため,HornSAT の各項の影響は局所的となり,コンピュータなどでの取扱いが容易となっている.しかし,CNFSAT は NP 完全問題であり,(CNF の構成によっては) CNF の充足可能性について,ある項が他の項と相互に依存するという構造を持つことがある.そのため,CNFSAT の各項の影響は局所的にはならない.その影響は CNF 全体に及ぶこと …

    情報処理学会論文誌. プログラミング 4(4), 45, 2011-09-22

    CiNii Link1

  • 6

    A PTAS for the Subset Sum Reconfiguration Problem

    Takehiro Ito , Erik D.Demaine

    … 整数の集合 A,容量 c のナップサック,整数 k に対し,要素の合計値 (以下,部分集合和という) が k 以上 c 以下になるような A の部分集合 (以下,パッキングという) を見つける問題は,部分集合和問題と呼ばれ,NP 完全であることが知られている.本論文では,与えられた 2 つのパッキング Ao と At の間を段階的に遷移させるシーケンスが存在するかどうか判定する問題を扱う.ここで,段階的な遷移シーケンスとは,以下の 3 …

    IPSJ SIG Notes 2011-AL-136(2), 1-8, 2011-08-30

    CiNii Link1

  • 7

    Visualization of the Phase Transition Phenomena on K-satisfiability Problem through Principal Component Analysis  [in Japanese]

    Yasuaki Akazawa , Masato Okada , Masato Inoue

    … 研究では,充足可能性問題 (random K-SAT 問題) の相転移現象を数値シミュレーションにより検証する.K-SAT 問題は標準的な NP 完全問題であるが,K-SAT 問題における相転移現象については未だ明らかになっていない.解析的には,系のサイズ (ブール変数の次元数) が無限大の場合に部分的に解かれているのみである.本研究では,Markov chain Monte Carlo(MCMC) シミュレーションと主成分分析 (PCA) を組み合わせた手法により,K-SAT 問題の系の …

    IPSJ SIG Notes. CVIM 2011-CVIM-178(26), 1-8, 2011-08-29

    CiNii Link1

  • 8

    NP-Completeness of Rolling Dice Puzzles Using Octahedral and Icosahedral Dices  [in Japanese]

    UEJIMA Akihiro , OKADA Takahiro

    … した問題について,その計算複雑さを議論する.6面ダイスと四角格子で定義されるRolling Cube PuzzleのNP完全性は既に証明されており,その先行研究において多角格子上での他の正多面体ダイスに関する未解決問題が提示されている.本論文では,その未解決問題の中から特に,正八面体及び正二十面体ダイスを三角格子上で回転移動させる問題について,既存結果の証明手法に倣い,それらのNP完全性を証明する. …

    The Transactions of the Institute of Electronics, Information and Communication Engineers. A J94-A(8), 621-628, 2011-08-01

    CiNii Fulltext PDF - Limited 

  • 9

    Complexity of the stamp folding problem

    Takuya Umesato , Toshiki Saitoh , Ryuhei Uehara , Hiro Ito

    … 化する問題と crease width の合計を最小化する問題である.この最小化問題は,数え上げ問題として定式化された.しかし,その計算量は知られていない.本研究では,始めに crease width の最大値を最小化する問題の強 NP 完全性を示す.次に crease width の合計を最小化する問題の解を求めるアルゴリズムを提案する.このアルゴリズムそのものは単純であるが,解析は自明ではない.そして,時間計算量が O(n2(n+kk))time であることを示す.こ …

    IPSJ SIG Notes 2011-AL-135(9), 1-7, 2011-05-09

    CiNii Link1

  • 10

    An Improved Result on Polynomial-Time Solvability of the Maximum Clique Problem  [in Japanese]

    NAKANISHI Hiroaki , TOMITA Etsuji

    … 典型的なNP完全問題である最大クリーク問題に対して,本論文では次の結果を示す.すなわち,節点数nの一般グラフにおいて,最大次数ΔがΔ≤2.613dlgn(d≥1:定数)なる条件を満たしているとき,このグラフの最大クリーク問題はO(n^<1+d>)なる多項式時間で可解である.ここで,特に定数d=1としたときにおける時間計算量O(n^2)は,節点数nに関してオーダとして最適である.これは,先に発表した結果(信学論(D),vol.J93-D,no.4,pp.417-425,April …

    The IEICE transactions on information and systems (Japanese edetion) J94-D(5), 843-851, 2011-05-01

    CiNii Fulltext PDF - Limited 

  • 11

    A Further Improved Result on Polynomial-Time Solvability of The Maximum Clique Problem  [in Japanese]

    NAKANISHI Hiroaki , TOMITA Etsuji , WAKATSUKI Mitsuo , NISHINO Tetsuro

    … NP完全である最大クリーク問題に対して,本稿では,"節点数nの一般グラフにおいて,最大次数ΔがΔ≦2.773dlgn(d≧0:定数)なる条件を満たしているとき,このグラフの最大クリーク問題はO(n^<1+d>)なる多項式時間で可解である."ことを示す.これは,先の発表結果(信学技報,COMP2010-43,pp.29-36)の改良であり,最大次数の上限に関する定数を一層増大させて,この定数2.773を得ている.更に,前発表ではd≧1であった条件をd≧0へと拡張し,dが …

    IEICE technical report. Theoretical foundations of Computing 111(20), 41-48, 2011-04-15

    CiNii Fulltext PDF - Limited 

  • 12

    Evaluation of metaheuristic algorithms for Spanning Tree Congestion  [in Japanese]

    MARUTA Daiki , OTACHI Yota , YAMAZAKI Koichi

    … 組み合わせ最適化問題の一つに全域木混雑度問題がある.全域木混雑度問題はNP完全であることが知られており,高速に最適解を得られるようなアルゴリズムは期待できない.全域木混雑度問題に対して各種メタヒューリスティックアルゴリズムを実装し,比較実験を行い,どの解法で有用な解を得られるのかを検証した.実験の結果,幅優先探索法と焼きなまし法,およびそれらのハイブリッド探索の優位性を確認した. …

    IEICE technical report. Theoretical foundations of Computing 110(464), 25-28, 2011-03-02

    CiNii Fulltext PDF - Limited 

  • 13

    Method of Locating Mirror Servers with Restricted Loads on Servers and Links  [in Japanese]

    NAKAMURA Ryota , MIWA Hiroyoshi

    … 御が行われている状況の下で,各サーバに対してそれを最近接サーバとして選択するノード数の上限(各サーバへの負荷抑制に対応)と,各リンクを通る経路数の上限(各リンクへの負荷抑制に対応)に関する制約を満たすサーバ配置を決定する問題を扱う.まず,この問題がNP完全であることを証明する.さらに近似アルゴリズムを設計し,現実の様々なネットワークに対して性能評価実験を行い,良好な性能が得られることを示す. …

    IEICE technical report 110(448), 753-758, 2011-02-24

    CiNii Fulltext PDF - Limited 

  • 14

    A Polynomial Time Algorithm for Restricted Edge Contraction of Partial <i>k</i>-trees  [in Japanese]

    Takashi Yamada , Takayoshi Shoudai

    … グラフ辺縮約問題とは,2 つのグラフ G と H を入力とするとき,G を辺縮約によって H に変換できるかを問う問題である.この問題は H が支配頂点を持たないならば NP 完全である.グラフ H の縮約不能頂点 v とは,辺縮約によって v へ同一視される G の頂点数がちょうど 1 となる頂点である.それ以外の頂点を縮約可能頂点と呼ぶ.本論文では,グラフ H の頂点のうち,独立かつ次数 2 の頂点を縮約可能頂点と指定することで,H …

    IPSJ SIG Notes 2011-AL-133(2), 1-8, 2011-01-05

    CiNii Link1

  • 15

    An Improved Result on Polynomial-Time Solvability of the Maximum Clique Problem  [in Japanese]

    NAKANISHI Hiroaki , TOMITA Etsuji

    … 典型的なNP完全問題である最大クリーク問題に対して,本稿では次の結果を示す.即ち,節点数nの一般グラフにおいて,最大次数ΔがΔ≦2.613dlgn(d≧1:定数)なる条件を満たしている時,このグラフの最大クリーク問題はO(n^<1+d>)なる多項式時間で可解である.ここで,特に定数d=1とした時における時間計算量O(n^2)は,節点数nに関してオーダとして最適である.これは,先に発表した結果(信学論D, vol.J93-D, no.4, pp.417-425)の直接的改良で …

    IEICE technical report. Theoretical foundations of Computing 110(325), 29-36, 2010-11-26

    CiNii Fulltext PDF - Limited 

  • 16

    Menu Selection and Bulk-Buying Ingredient Selection Algorithms for Home Cooking Support by Busy Persons  [in Japanese]

    TANIGUCHI Shiho , FUNABIKI Nobuo , NAKANISHI Toru

    … ことが考えられる.平日には,まとめ買いできない食材の購入と,仕上げ調理のみを行うことで,時間短縮が可能となる.本論文では,この2段階調理のための献立選択アルゴリズムおよびまとめ買い選択アルゴリズムの提案を行う.これらの問題は,NP完全問題であるナップサック問題から帰着できることから,その貪欲法に基づくアルゴリズムとしている.例題に対するシミュレーションにより,各提案アルゴリズムの有効性を示す. …

    IEICE technical report. Artificial intelligence and knowledge-based processing 110(301), 25-30, 2010-11-12

    CiNii Fulltext PDF - Limited  References (5)

  • 17

    Graph Classes and Subgraph Isomorphism  [in Japanese]

    Toshiki Saitoh , Yota Otachi , Shuji Kijima , Takeaki Uno

    部分グラフ同型性判定問題は 2 つのグラフ G と H が与えられたとき,G を H に埋め込めるかどうかを判定する問題である.この問題は,ハミルトンパス問題や最大クリーク問題など多くの NP-完全な問題を含んでいるため,一般のグラフ上だけでなく,二つのグラフを連結な平面グラフに制限しても NP-完全である.本論文では,ハミルトンパス問題や最大クリーク問題,同型性判定問題を多項式時間で解くことがで …

    IPSJ SIG Notes 2010-AL-132(5), 1-8, 2010-11-12

    CiNii Link1

  • 18

    On the completely independent spanning trees in <i>k</i>-trees  [in Japanese]

    Masayoshi Matsushita , Toru Araki

    … T1,T2 を連結グラフ G の二つの全域木とする.G の任意の 2 頂点 u,v に対して,T1 上の u-v パスと T2 上の u-v パスが,両端点以外に共通の頂点を持たないとき,T1 と T2 は互いに完全独立であるという.本論文では,以下の結果を証明した.(1) 与えられたグラフに 2 個の完全独立全域木が存在するかどうかを判定する問題は,入力をコーダルグラフに限定しても NP 完全である.(2) k ? …

    IPSJ SIG Notes 2010-AL-131(2), 1-4, 2010-09-15

    CiNii Link1 References (6)

  • 19

    Developments of the Node Configuration Problem for WDM Ring Networks  [in Japanese]

    Megumi Isogai , Nobuo Funabiki , Toru Nakanishi

    … に着目し,その通信性能の向上を目的として,ノード毎の送受信器追加割当と受信波長割当を行うノード構成問題とそのアルゴリズムの研究を進めている.本論文では,まず,ノード構成問題の判定問題の NP 完全性を,既存の NP 完全問題であるビンパッキング問題からの帰着により証明する.また,提案しているノード構成アルゴリズムに基づき,スループットを極大とする追加送受信器数の推定法を提案する. …

    IPSJ SIG Notes 2010-DPS-144(3), 1-8, 2010-09-10

    CiNii Link1 References (8)

  • 20

    NP-completeness of generalized Kaboozle

    Tetsuo Asano , Erik D.Demaine , Martin L.Demaine , Ryuhei Uehara

    … て,特定の色のパスの両端点をその色の 1 本のパスでつなぐことである.カードの裏表・回転・順序という自由度があるので,この問題が一般に NP 完全であることは容易に想像できる.本稿では,これら 3 種類の自由度のどれか 1 つを使うだけで,この問題が NP 完全であることを示す.さらに Kaboozle を全部つなぎ合わせて 1 次元上の問題に制限する.具体的には,すべてのカードを帯状につなぎ合わせ,しかも …

    IPSJ SIG Notes 2010-AL-130(3), 1-6, 2010-05-12

    CiNii Link1 References (10)