Search Results:　 1-20 of 574

  • 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

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

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

    CiNii Link1

  • 6

    The Complexity of Free Flood Filling Games

    Hiroyuki Fukui , Akihiro Nakanishi , Ryuhei Uehara , Takeaki Uno , Yushi Uno

    … In this paper, we show that the free Flood-It is NP-complete on trees with only three colors, and it is polynomial time solvable on paths and cycles with any number of colors. …

    IPSJ SIG Notes 2011-AL-136(7), 1-5, 2011-08-30

    CiNii Link1

  • 7

    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

  • 8

    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

  • 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

    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 

  • 11

    <i>k</i>-cyclic Orientations of Graphs

    Yasuaki Kobayashi , Yuichiro Miyamoto , Hisao Tamaki

    … We show that this problem is NP-complete for every fixed k ? …

    IPSJ SIG Notes 2011-AL-134(6), 1-8, 2011-02-28

    CiNii Link1

  • 12

    Hardness and FPT Algorithm for the Rainbow Connectivity of Graphs

    Takanori Aoki , Takehiro Ito , Akira Suzuki , Kei Uchizawa , Xiao Zhou

    … The first is to show that the problem is strongly NP-complete even for outerplanar graphs. … We also show that the problem is strongly NP-complete for graphs of diameter 2. …

    IPSJ SIG Notes 2011-AL-134(4), 1-8, 2011-02-28

    CiNii Link1

  • 13

    Control Method of Autonomously Formed Unstructured P2P Network Based on Usage History  [in Japanese]

    OGURA Keishi , NIWA Hiroyoshi

    クライアント/サーバ型と対照的なネットワーク形態であるP2P(Peer-to-Peer)型のネットワークが,ファイル共有だけでなく,分散ストレージやコンテンツ配信等,様々な分野での応用に期待されている.一般に,P2Pネットワークはシステム全体を管理する機構を持たない自律分散型システムであるため,目的のファイルを検索することが容易ではない.そのための方法として,なんらかのネットワーク構造を形成して分 …

    IEICE technical report. Information networks 110(449), 371-376, 2011-02-24

    CiNii Fulltext PDF - Limited 

  • 14

    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 

  • 15

    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

  • 16

    Network Design Methods for Minimizing Number of Links Added to a Network to Alleviate Performance Degradation Following a Link Failure

    KATAYAMA Nozomu , FUJIMURA Takeshi , MIWA Hiroyoshi , KAMIYAMA Noriaki , HASEGAWA Haruhisa , YOSHINO Hideaki

    … Next, we prove that this problem is NP-complete and present two approximation algorithms for the optimization problem so as to minimize the number of links added. …

    IEICE Transactions on Communications E94.B(6), 1630-1639, 2011

    J-STAGE CrossRef

  • 17

    Chordal Graph Based Channel Assignment for Multicast and Unicast Traffic in Wireless Mesh Networks

    JIN Junfeng , JI Yusheng , ZHAO Baohua , ZHOU Hao

    … However, most of the past works focus on vertex coloring of a general contention graph, which is NP-Complete, and use the greedy algorithm to achieve a suboptimal result. …

    IEICE Transactions on Communications 93(12), 3409-3416, 2010-12-01

    J-STAGE CrossRef References (24)

  • 18

    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 

  • 19

    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)

  • 20

    Bandwidth of Convex Bipartite Graphs and Related Graph Classes

    Anish ManSinghShrestha , Satoshi Tayu , Shuichi Ueno

    … It is known that the bandwidth problem is NP-complete for chordal bipartite graphs, while the problem can be solved in polynomial time for bipartite permutation graphs, which is a subclass of chordal bipartite graphs. … This paper shows that the problem is NP-complete even for convex bipartite graphs, a subclass of chordal bipartite graphs and a superclass of bipartite permutation graphs. …

    IPSJ SIG Notes 2010-AL-132(6), 1-7, 2010-11-12

    CiNii Link1