Search Results 1-20 of 208

  • Program File Placement Problem for Machine-to-Machine Service Network Platform

    SATO Takehiro , OKI Eiji

    … We prove that the decision version of the PFP problem is NP-complete. …

    IEICE Transactions on Communications E102.B(3), 418-428, 2019

    IR J-STAGE

  • Program file placement problem for machine-to-machine service network platform

    SATO Takehiro , OKI Eiji

    … We prove that the decision version of the PFP problem is NP-complete. …

    IEICE Transactions on Communications, 2018

    J-STAGE

  • An Efficient Pattern Matching Algorithm for Unordered Term Tree Patterns of Bounded Dimension

    SHOUDAI Takayoshi , MIYAHARA Tetsuhiro , UCHIDA Tomoyuki , MATSUMOTO Satoshi , SUZUKI Yusuke

    … is NP-complete if the dimension of <i>t</i> …

    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E101.A(9), 1344-1354, 2018

    J-STAGE

  • The Building Puzzle Is Still Hard Even in the Single Lined Version

    Kazuya Haraguchi , Ryoya Tanaka

    … Recently, Iwamoto and Matsui showed the NP-completeness of the decision problem version of this puzzle, which asks whether a given instance has a solution or not. … it is still NP-complete to decide whether we can complete a single line of the grid (i.e., a 1 × n or an n × 1 subgrid) without violating the rule.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). …

    情報処理学会論文誌 58(8), 2017-08-15

    IPSJ

  • Simple Folding is Really Hard

    Hugo A. Akitaya , Erik D. Demaine , Jason S. Ku

    … We prove strong NP-completeness of deciding whether a crease pattern can be simply folded, both for orthogonal paper with assigned orthogonal creases and for square paper with assigned or unassigned creases at multiples of 45°. … These results settle a long standing open problem, where weak NP-hardness was established for a subset of the models considered here, leaving open the possibility of pseudopolynomial-time algorithms. …

    情報処理学会論文誌 58(8), 2017-08-15

    IPSJ

  • Total Tetris: Tetris with Monominoes, Dominoes, Trominoes, Pentominoes,...

    Erik D. Demaine , Martin L. Demaine , Sarah Eisenstat , Adam Hesterberg , Andrea Lincoln , Jayson Lynch , Y. William Yu

    … We prove that it is NP-complete to survive or clear a given initial board with a given sequence of pieces for each k ≥ 5, complementing the previous NP-completeness result for k=4. … More surprisingly, we show that board clearing is NP-complete for k=3; … and if pieces may not be rotated, then clearing is NP-complete for k=2 and survival is NP-complete for k=3. …

    情報処理学会論文誌 58(8), 2017-08-15

    IPSJ

  • The Building Puzzle Is Still Hard Even in the Single Lined Version

    Haraguchi Kazuya , Tanaka Ryoya

    … Recently, Iwamoto and Matsui showed the NP-completeness of the decision problem version of this puzzle, which asks whether a given instance has a solution or not. … it is still NP-complete to decide whether we can complete a single line of the grid (i.e., a 1 × <i>n</i> …

    Journal of Information Processing 25(0), 730-734, 2017

    IR J-STAGE

  • Simple Folding is Really Hard

    A. Akitaya Hugo , D. Demaine Erik , S. Ku Jason

    … We prove strong NP-completeness of deciding whether a crease pattern can be simply folded, both for orthogonal paper with assigned orthogonal creases and for square paper with assigned or unassigned creases at multiples of 45<sup>°</sup>. … These results settle a long standing open problem, where weak NP-hardness was established for a subset of the models considered here, leaving open the possibility of pseudopolynomial-time algorithms. …

    Journal of Information Processing 25(0), 580-589, 2017

    J-STAGE

  • Total Tetris: Tetris with Monominoes, Dominoes, Trominoes, Pentominoes,...

    Demaine Erik D. , Demaine Martin L. , Eisenstat Sarah , Hesterberg Adam , Lincoln Andrea , Lynch Jayson , Yu Y. William

    … We prove that it is NP-complete to survive or clear a given initial board with a given sequence of pieces for each <i>k</i> … ≥ 5, complementing the previous NP-completeness result for <i>k</i>=4. … More surprisingly, we show that board clearing is NP-complete for <i>k</i>=3; …

    Journal of Information Processing 25(0), 515-527, 2017

    J-STAGE

  • An Exact Algorithm for Lowest Edge Dominating Set

    IWAIDE Ken , NAGAMOCHI Hiroshi

    … is adjacent to some edge in <i>F</i>, and computing the minimum size of an edge dominating set is known to be NP-hard. … In this paper, we prove that the problem is NP-complete, whereas we design an <i>O</i><sup>*</sup>(2.0801<sup>µ(<i>G</i>)/2</sup>)-time and polynomial-space algorithm to the problem.</p> …

    IEICE Transactions on Information and Systems E100.D(3), 414-421, 2017

    J-STAGE

  • Single-Player and Two-Player Buttons & Scissors Games

    Burke Kyle , Demaine Erik D. , Hearn Robert A. , Hesterberg Adam , Hoffman Michael , Ito Hiro , Kostitsyna Irina , Loffler Maarten , Uno Yushi , Schmidt Christiane , Uehara Ryuhei , Williams Aaron

    … The Buttons and Scissors puzzle was recently shown to be NP-hard. … For example, we show that it is NP-hard when the puzzle consists of C=2 colors, and polytime solvable for C=1. … Similarly, it is NP-hard when each color is used by at most F=4 buttons, and polytime solvable for F=3. …

    Lecture Notes in Computer Science 9943, 60-72, 2016-11-24

    IR DOI

  • Polynomial time reduction from 3SAT to solving low first fall degree multivariable cubic equations system  [in Japanese]

    長尾 孝一

    … [2] shows that the problem for deciding whether the value of Semaev's formula Sm (x1, ..., xm) is 0 or not, is NP-complete. … This result directly does not means ECDLP being NPcomplete, but, it suggests ECDLP being NP-complete. … And so, suppose P ≠ NP, which almost all researcher assume this, it has a contradiction and we see that first fall degree assumption is not true. …

    研究報告 = Journal of technological researches 59(106), 1-5, 2016-03

    IR

  • Computational complexity in the design of voting rules

    Takamiya Koji , Tanaka Akira

    … We prove that it is an NP-complete problem to decide whether a given simple game is stable, or not. …

    Theory and decision 80(1), 33-41, 2016-01

    IR DOI

  • Swapping Colored Tokens on Graphs

    Yamanaka Katsuhisa , Horiyama Takashi , Kirkpatrick David , Otachi Yota , Saitoh Toshiki , Uehara Ryuhei , Uno Yushi

    … We show that c-Colored Token Swapping is NP-complete for every constant c>3 even if input graphs are restricted to connected planar bipartite graphs of maximum degree 3. …

    Lecture Notes in Computer Science 9214, 619-628, 2015-08-05

    IR DOI

  • Competitive Diffusion on Weighted Graphs

    Ito Takehiro , Otachi Yota , Saitoh Toshiki , Satoh Hisayuki , Suzuki Akira , Uchizawa Kei , Uehara Ryuhei , Yamanaka Katsuhisa , Zhou Xiao

    … We also show that the problem is NP-hard even for series-parallel graphs with positive integer weights, and is NP-hard even for forests with arbitrary integer weights. …

    Lecture Notes in Computer Science 9214, 422-433, 2015-08-05

    IR DOI

  • NP-completeness of Routing Problem with Bend Constraint  [in Japanese]

    本江 俊幸 , 高橋 篤司

    電子情報通信学会技術研究報告 = IEICE technical report : 信学技報 115(21), 13-18, 2015-05-14

  • NP-completeness of Routing Problem with Bend Constraint  [in Japanese]

    本江 俊幸 , 高橋 篤司

    … 工程に対応する配線は,分岐は許されず,さらに折れ曲がりが禁止されるグリッドが存在する.そのため,最終工程に対応する配線パターンを生成するために,3 色グリッドに対応するグラフ上で折れ曲がり制約を満たす 2 点間のパスを求めるアルゴリズムが必要となる.本稿では,グラフ上に折れ曲がり制約が与えられたとき,一般に,2 点間に折れ曲がり制約を満たすパスが存在するか否かの判定問題は NP 完全であることを示す. …

    情報処理学会研究報告. SLDM, [システムLSI設計技術] 2015-SLDM-171(3), 1-6, 2015-05-07

    IPSJ

  • NP-hardness of Finding Minimum Test Set for Detecting Stuck-at and/or Bridging Faults in a Reversible Circuit  [in Japanese]

    TAKAKURA Hibiki , YAMADA Toshinori

    … るためとても魅力的であり,様々な分野に応用が期待できる.よって,可逆回路製造時に回路内の故障を発見することはとても重要である.可逆回路内で短絡故障と縮退故障の両方を検出するための,最小検査入力集合を生成する問題の複雑さについての研究は,著者らの知る限りこれまで行われていない.本研究では,可逆回路に対し縮退および短絡故障を検出する最小の検査入力集合を生成することがNP-困難であることを示す. …

    IEICE technical report. Theoretical foundations of Computing 114(509), 47-51, 2015-03-09

  • Folding a Paper Strip to Minimize Thickness

    Demaine Erik D. , Eppstein David , Hesterberg Adam , Ito Hiro , Lubiw Anna , Uehara Ryuhei , Uno Yushi

    In this paper, we study how to fold a specified origami crease pattern in order to minimize the impact of paper thickness. Specifically, origami designs are often expressed by a mountain-valley patter …

    Lecture Notes in Computer Science 8973, 113-124, 2015-02-26

    IR DOI

  • An Efficient Pattern Matching Algorithm for Ordered Term Tree Patterns

    SUZUKI Yusuke , SHOUDAI Takayoshi , UCHIDA Tomoyuki , MIYAHARA Tetsuhiro

    … We show that Matching problem for term tree patterns in $\ott$ is NP-complete, by giving a reduction from the string pattern matching problem, which is NP-complete. …

    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E98.A(6), 1197-1211, 2015

    J-STAGE

Page Top