IEICE Trans

Keyword : NP-complete

Moon-or-Sun, Nagareru, and Nurimeizu are NP-Complete Chuzo IWAMOTO Tatsuya IDE
Publication: Publication Date: 2022/09/01 Vol. E105-A No. 9 ; pp. 1187-1194 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Algorithms and Data Structures Keyword: Moon-or-Sun, Nagareru, Nurimeizu, pencil puzzle, NP-complete,
	Summary \| Full Text:PDF

Five Cells and Tilepaint are NP-Complete Chuzo IWAMOTO Tatsuya IDE
Publication: Publication Date: 2022/03/01 Vol. E105-D No. 3 ; pp. 508-516 Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science - New Trends of Theory of Computation and Algorithm -) Category: Keyword: Five Cells, Tilepaint, pencil puzzle, NP-complete,
	Summary \| Full Text:PDF

Computational Complexity of Nurimisaki and Sashigane Chuzo IWAMOTO Tatsuya IDE
Publication: Publication Date: 2020/10/01 Vol. E103-A No. 10 ; pp. 1183-1192 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: complexity theory Keyword: Nurimisaki, Sashigane, pencil puzzle, NP-complete,
	Summary \| Full Text:PDF

Polynomial-Time Reductions from 3SAT to Kurotto and Juosan Puzzles Chuzo IWAMOTO Tatsuaki IBUSUKI
Publication: Publication Date: 2020/03/01 Vol. E103-D No. 3 ; pp. 500-505 Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — Frontiers of Theory of Computation and Algorithm —) Category: Keyword: Kurotto, Juosan, pencil puzzle, NP-complete,
	Summary \| Full Text:PDF

Computational Complexity of Herugolf and Makaro Chuzo IWAMOTO Masato HARUISHI Tatsuaki IBUSUKI
Publication: Publication Date: 2019/09/01 Vol. E102-A No. 9 ; pp. 1118-1125 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Puzzles Keyword: Herugolf, Makaro, pencil puzzle, NP-complete,
	Summary \| Full Text:PDF

Computational Complexity of Usowan Puzzles Chuzo IWAMOTO Masato HARUISHI
Publication: Publication Date: 2018/09/01 Vol. E101-A No. 9 ; pp. 1537-1540 Type of Manuscript: Special Section LETTER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: Usowan, pencil puzzle, NP-complete,
	Summary \| Full Text:PDF

On the Three-Dimensional Channel Routing Satoshi TAYU Toshihiko TAKAHASHI Eita KOBAYASHI Shuichi UENO
Publication: IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Publication Date: 2016/10/01 Vol. E99-A No. 10 ; pp. 1813-1821 Type of Manuscript: PAPER Category: Graphs and Networks Keyword: 3-D channel, NP-complete, routing algorithm, Steiner tree,
	Summary \| Full Text:PDF

Computational Complexity of Building Puzzles Chuzo IWAMOTO Yuta MATSUI
Publication: IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Publication Date: 2016/06/01 Vol. E99-A No. 6 ; pp. 1145-1148 Type of Manuscript: Special Section LETTER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: building puzzle, pencil puzzle, NP-complete,
	Summary \| Full Text:PDF

An Access-Point Aggregation Approach for Energy-Saving Wireless Local Area Networks Md. Ezharul ISLAM Nobuo FUNABIKI Toru NAKANISHI Kan WATANABE
Publication: IEICE TRANSACTIONS on Communications Publication Date: 2013/12/01 Vol. E96-B No. 12 ; pp. 2986-2997 Type of Manuscript: Special Section PAPER (Special Section on Network and System Technologies for Sustainable Society) Category: Keyword: wireless local area network, access-point aggregation, NP-complete, algorithm, energy-saving, IEEE 802.11n,
	Summary \| Full Text:PDF

Generalized Pyramid is NP-Complete Chuzo IWAMOTO Yuta MATSUI
Publication: IEICE TRANSACTIONS on Information and Systems Publication Date: 2013/11/01 Vol. E96-D No. 11 ; pp. 2462-2465 Type of Manuscript: LETTER Category: Fundamentals of Information Systems Keyword: NP-complete, computational complexity, one-player game, pyramid,
	Summary \| Full Text:PDF

Generalized Shisen-Sho is NP-Complete Chuzo IWAMOTO Yoshihiro WADA Kenichi MORITA
Publication: IEICE TRANSACTIONS on Information and Systems Publication Date: 2012/11/01 Vol. E95-D No. 11 ; pp. 2712-2715 Type of Manuscript: LETTER Category: Fundamentals of Information Systems Keyword: NP-complete, computational complexity, one-player game, Shisen-Sho,
	Summary \| Full Text:PDF

Network Design Methods for Minimizing Number of Links Added to a Network to Alleviate Performance Degradation Following a Link Failure Nozomu KATAYAMA Takeshi FUJIMURA Hiroyoshi MIWA Noriaki KAMIYAMA Haruhisa HASEGAWA Hideaki YOSHINO
Publication: IEICE TRANSACTIONS on Communications Publication Date: 2011/06/01 Vol. E94-B No. 6 ; pp. 1630-1639 Type of Manuscript: PAPER Category: Fundamental Theories for Communications Keyword: quality of service, backbone network, optimization problem, NP-complete, approximation algorithm,
	Summary \| Full Text:PDF

A WDS Clustering Algorithm for Wireless Mesh Networks Shigeto TAJIMA Nobuo FUNABIKI Teruo HIGASHINO
Publication: IEICE TRANSACTIONS on Information and Systems Publication Date: 2010/04/01 Vol. E93-D No. 4 ; pp. 800-810 Type of Manuscript: PAPER Category: Fundamentals of Information Systems Keyword: wireless mesh network, WDS clustering, gateway selection, NP-complete, heuristic algorithm, variable depth search,
	Summary \| Full Text:PDF

A Novel Resource Allocation and Admission Control in LTE Systems Abhishek ROY Navrati SAXENA Jitae SHIN
Publication: IEICE TRANSACTIONS on Communications Publication Date: 2010/03/01 Vol. E93-B No. 3 ; pp. 721-724 Type of Manuscript: LETTER Category: Network Keyword: LTE, resource allocation, admission control, reneging, NP-complete, dynamic programming, greedy,
	Summary \| Full Text:PDF

Near-Optimal Auto-Configuration of PCID in LTE Cellular Systems Navrati SAXENA Abhishek ROY Jeong Jae WON
Publication: IEICE TRANSACTIONS on Communications Publication Date: 2009/10/01 Vol. E92-B No. 10 ; pp. 3252-3255 Type of Manuscript: LETTER Category: Network Keyword: LTE, SON, vertex coloring, NP-complete, permutation, randomized algorithms,
	Summary \| Full Text:PDF

An Access Point Allocation Algorithm for Indoor Environments in Wireless Mesh Networks Tamer FARAG Nobuo FUNABIKI Toru NAKANISHI
Publication: IEICE TRANSACTIONS on Communications Publication Date: 2009/03/01 Vol. E92-B No. 3 ; pp. 784-793 Type of Manuscript: Special Section PAPER (Special Section on Ad Hoc and Mesh Networking for Next Generation Access Systems) Category: Keyword: access point allocation, wireless mesh network, algorithm, indoor environment, NP-complete,
	Summary \| Full Text:PDF

On Fault Testing for Reversible Circuits Satoshi TAYU Shigeru ITO Shuichi UENO
Publication: IEICE TRANSACTIONS on Information and Systems Publication Date: 2008/12/01 Vol. E91-D No. 12 ; pp. 2770-2775 Type of Manuscript: PAPER Category: Complexity Theory Keyword: 3-SAT, CNOT gate, complete test set, fault testing, NP-complete, reversible circuit, stuck-at fault, test vector,
	Summary \| Full Text:PDF

An Optimal Share Transfer Problem on Secret Sharing Storage Systems Toshiyuki MIYAMOTO Sadatoshi KUMAGAI
Publication: IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Publication Date: 2007/11/01 Vol. E90-A No. 11 ; pp. 2458-2464 Type of Manuscript: Special Section PAPER (Special Section on Concurrent/Hybrid Systems: Theory and Applications) Category: Keyword: distributed storage system, secret sharing scheme, Steiner tree, NP-complete, distributed algorithm,
	Summary \| Full Text:PDF

Optimal Euler Circuit of Maximum Contiguous Cost Yu QIAO Makoto YASUHARA
Publication: IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Publication Date: 2007/01/01 Vol. E90-A No. 1 ; pp. 274-280 Type of Manuscript: PAPER Category: Graphs and Networks Keyword: Optimal Euler Circuit, Euler circuit, graph theory, contiguous cost, NP-complete, approximation algorithm,
	Summary \| Full Text:PDF

A Minimum Dead Space Algorithm for Generalized Isochronous Channel Reuse Problems in DQDB Networks Nobuo FUNABIKI Jun KAWASHIMA Kiyohiko OKAYAMA Toru NAKANISHI Teruo HIGASHINO
Publication: IEICE TRANSACTIONS on Communications Publication Date: 2004/09/01 Vol. E87-B No. 9 ; pp. 2692-2698 Type of Manuscript: PAPER Category: Network Keyword: ICRP, heuristic algorithm, minimum dead space, NP-complete, IEEE 802.6, DQDB,
	Summary \| Full Text:PDF

The Design and Evaluation of Data-Dependent Hardware for Subgraph Isomorphism Problem Shoji YAMAMOTO Shuichi ICHIKAWA Hiroshi YAMAMOTO
Publication: IEICE TRANSACTIONS on Information and Systems Publication Date: 2004/08/01 Vol. E87-D No. 8 ; pp. 2038-2047 Type of Manuscript: Special Section PAPER (Special Section on Reconfigurable Systems) Category: Recornfigurable Systems Keyword: FPGA, custom circuit, graph algorithm, NP-complete, partial evaluation,
	Summary \| Full Text:PDF

P2PMM_router: A Two-Stage Heuristic Algorithm to Peer-to-Peer Multicast Routing Problems in Multihome Networks Nobuo FUNABIKI Jun KAWASHIMA Shoji YOSHIDA Kiyohiko OKAYAMA Toru NAKANISHI Teruo HIGASHINO
Publication: IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Publication Date: 2004/05/01 Vol. E87-A No. 5 ; pp. 1070-1076 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: peer-to-peer multicast, real-time communication, multihome network, heuristic algorithm, NP-complete,
	Summary \| Full Text:PDF

Trade-Offs in Custom Circuit Designs for Subgraph Isomorphism Problems Shuichi ICHIKAWA Hidemitsu SAITO Lerdtanaseangtham UDORN Kouji KONISHI
Publication: IEICE TRANSACTIONS on Information and Systems Publication Date: 2003/07/01 Vol. E86-D No. 7 ; pp. 1250-1257 Type of Manuscript: PAPER Category: VLSI Systems Keyword: NP-complete, graph, algorithm, FPGA,
	Summary \| Full Text:PDF

Data Dependent Circuit for Subgraph Isomorphism Problem Shuichi ICHIKAWA Shoji YAMAMOTO
Publication: IEICE TRANSACTIONS on Information and Systems Publication Date: 2003/05/01 Vol. E86-D No. 5 ; pp. 796-802 Type of Manuscript: Special Section PAPER (Special Issue on Reconfigurable Computing) Category: Keyword: NP-complete, custom circuit, FPGA, graph algorithm,
	Summary \| Full Text:PDF

Complexity and Completeness of Finding Another Solution and Its Application to Puzzles Takayuki YATO Takahiro SETA
Publication: IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Publication Date: 2003/05/01 Vol. E86-A No. 5 ; pp. 1052-1060 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: computational complexity, NP-complete, another solution, puzzle,
	Summary \| Full Text:PDF

On Finding Feasible Solutions for the Group Multicast Routing Problem Chor Ping LOW Ning WANG
Publication: IEICE TRANSACTIONS on Communications Publication Date: 2002/01/01 Vol. E85-B No. 1 ; pp. 268-277 Type of Manuscript: PAPER Category: Network Keyword: group multicast routing, heuristic algorithms, bandwidth constraint, NP-complete,
	Summary \| Full Text:PDF

NP-Completeness of Reallocation Problems with Restricted Block Volume Hiroyoshi MIWA Hiro ITO
Publication: IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Publication Date: 2000/04/25 Vol. E83-A No. 4 ; pp. 590-597 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: reallocation, computational complexity, NP-complete, SAT, steiner tree problem,
	Summary \| Full Text:PDF

A Two-Stage Discrete Optimization Method for Largest Common Subgraph Problems Nobuo FUNABIKI Junji KITAMICHI
Publication: IEICE TRANSACTIONS on Information and Systems Publication Date: 1999/08/25 Vol. E82-D No. 8 ; pp. 1145-1153 Type of Manuscript: PAPER Category: Algorithm and Computational Complexity Keyword: common subgraph, isomorphic, NP-complete, greedy method, discrete descent method, simulated annealing,
	Summary \| Full Text:PDF

The Complexity of an Optimal File Transfer Problem Yoshihiro KANEKO Shoji SHINODA
Publication: IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Publication Date: 1999/02/25 Vol. E82-A No. 2 ; pp. 394-397 Type of Manuscript: LETTER Category: Graphs and Networks Keyword: file transmission net, file transfer, Steiner tree, NP-complete,
	Summary \| Full Text:PDF

Sparse Spanning Subgraphs Preserving Connectivity and Distance between Vertices and Vertex Subsets Hiroyoshi MIWA Hiro ITO
Publication: IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Publication Date: 1998/05/25 Vol. E81-A No. 5 ; pp. 832-841 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: graph, area graph, diameter, distance, connectivity, NP-complete, polynomial time, algorithm,
	Summary \| Full Text:PDF

A Neural-Greedy Combination Algorithm for Board-Level Routing in FPGA-Based Logic Emulation Systems Nobuo FUNABIKI Junji KITAMICHI
Publication: IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Publication Date: 1998/05/25 Vol. E81-A No. 5 ; pp. 866-872 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: FPGA, board-level routing, NP-complete, digital neural network, greedy algorithm,
	Summary \| Full Text:PDF

Covering Problems in the p-Collection Problems Kaoru WATANABE Masakazu SENGOKU Hiroshi TAMURA Shoji SHINODA
Publication: IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Publication Date: 1998/03/25 Vol. E81-A No. 3 ; pp. 470-475 Type of Manuscript: Special Section PAPER (Special Section of Selected Papers from the 10th Karuizawa Workshop on Circuits and Systems) Category: Keyword: location problem, network flows, NP-complete, optimization problem,
	Summary \| Full Text:PDF

A Digital Neural Network for Multilayer Channel Routing with Crosstalk Minimization Nobuo FUNABIKI Junji KITAMICHI Seishi NISHIKAWA
Publication: IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Publication Date: 1997/09/25 Vol. E80-A No. 9 ; pp. 1704-1713 Type of Manuscript: PAPER Category: Neural Networks Keyword: crosstalk, multilayer channel routing, neural network, digital technology, NP-complete,
	Summary \| Full Text:PDF

A Massive Digital Neural Network for Total Coloring Problems Nobuo FUNABIKI Junji KITAMICHI Seishi NISHIKAWA
Publication: IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Publication Date: 1997/09/25 Vol. E80-A No. 9 ; pp. 1625-1629 Type of Manuscript: Special Section LETTER (Special Section on Nonlinear Theory and its Applications) Category: Keyword: neural network, digital technology, total coloring, NP-complete, combinatorial optimization,
	Summary \| Full Text:PDF

The p-Collection Problem in a Flow Network with Lower Bounds Kaoru WATANABE Hiroshi TAMURA Keisuke NAKANO Masakazu SENGOKU
Publication: IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Publication Date: 1997/04/25 Vol. E80-A No. 4 ; pp. 651-657 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: location problem, network flows, NP-complete, optimization problem,
	Summary \| Full Text:PDF

A Linear-Time Algorithm for Determining the Order of Moving Products in Realloction Problems Hiroyoshi MIWA Hiro ITO
Publication: IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Publication Date: 1997/03/25 Vol. E80-A No. 3 ; pp. 534-543 Type of Manuscript: Special Section PAPER (Special Section of Selected Papers from the 9th Karuizawa Workshop on Circuits and Systems) Category: Keyword: graph, reallocation, linear-time, NP-complete,
	Summary \| Full Text:PDF

Solving Combinatorial Optimization Problems Using the Oscillatory Neural Network Yoshiaki WATANABE Keiichi YOSHINO Tetsuro KAKESHITA
Publication: IEICE TRANSACTIONS on Information and Systems Publication Date: 1997/01/25 Vol. E80-D No. 1 ; pp. 72-77 Type of Manuscript: PAPER Category: Bio-Cybernetics and Neurocomputing Keyword: neural network, optimization problem, NP-complete,
	Summary \| Full Text:PDF

The Problem of where to Locate p-Sinks in a Flow Network: Complexity Approach Kaoru WATANABE Hiroshi TAMURA Masakazu SENGOKU
Publication: IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Publication Date: 1996/09/25 Vol. E79-A No. 9 ; pp. 1495-1503 Type of Manuscript: PAPER Category: Graphs and Networks Keyword: location problem, flow network, NP-complete, optimization problem,
	Summary \| Full Text:PDF

A Binary Neural Network Approach for Link Activation Problems in Multihop Radio Networks Nobuo FUNABIKI Seishi NISHIKAWA
Publication: IEICE TRANSACTIONS on Communications Publication Date: 1996/08/25 Vol. E79-B No. 8 ; pp. 1086-1093 Type of Manuscript: PAPER Category: Communication Networks and Services Keyword: multihop radio network, link activation, NP-complete, neural network, parallel algorithm,
	Summary \| Full Text:PDF

Complexity and Algorithm for Reallocation Problem Hiroyoshi MIWA Hiro ITO
Publication: IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Publication Date: 1996/04/25 Vol. E79-A No. 4 ; pp. 461-468 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: reallocation, graph, linear time, NP-complete,
	Summary \| Full Text:PDF

The Complexity of the Optimal Variable Ordering Problems of a Shared Binary Decision Diagram Seiichiro TANI Kiyoharu HAMAGUCHI Shuzo YAJIMA
Publication: IEICE TRANSACTIONS on Information and Systems Publication Date: 1996/04/25 Vol. E79-D No. 4 ; pp. 271-281 Type of Manuscript: PAPER Category: Algorithm and Computational Complexity Keyword: ordered binary decision diagram, variable ordering, optimal linear arrangement, NP-complete, Boolean function,
	Summary \| Full Text:PDF

Comparisons of Energy-Descent Optimization Algorithms for Maximum Clique Problems Nobuo FUNABIKI Seishi NISHIKAWA
Publication: IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Publication Date: 1996/04/25 Vol. E79-A No. 4 ; pp. 452-460 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: maximum clique, NP-complete, neural network, algorithm, energy-descent opimization,
	Summary \| Full Text:PDF

The Complexity of Drawing Tree-Structured Diagrams Kensei TSUCHIDA
Publication: IEICE TRANSACTIONS on Information and Systems Publication Date: 1995/07/25 Vol. E78-D No. 7 ; pp. 901-908 Type of Manuscript: PAPER Category: Algorithm and Computational Complexity Keyword: graph drawing, tree-structured diagrams, NP-complete, constraints for tree drawing,
	Summary \| Full Text:PDF

Complexity of Finding Alphabet Indexing Shinichi SHIMOZONO Satoru MIYANO
Publication: IEICE TRANSACTIONS on Information and Systems Publication Date: 1995/01/25 Vol. E78-D No. 1 ; pp. 13-18 Type of Manuscript: PAPER Category: Algorithm and Computational Complexity Keyword: algorithm and computational complexity, alphabet indexing, local search algorithm, NP-complete, PLS-complete,
	Summary \| Full Text:PDF

On the Complexity of Protocol Validation Problems for Protocols with Bounded Capacity Channels Yoshiaki KAKUDA Yoshihiro TAKADA Tohru KIKUNO
Publication: IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Publication Date: 1994/04/25 Vol. E77-A No. 4 ; pp. 658-667 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: computational complexity, deadlock, NP-complete, protocol, protocol validation,
	Summary \| Full Text:PDF

A Polynomial Time Algorithm for Finding a Largest Common Subgraph of almost Trees of Bounded Degree Tatsuya AKUTSU
Publication: IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Publication Date: 1993/09/25 Vol. E76-A No. 9 ; pp. 1488-1493 Type of Manuscript: PAPER Category: Algorithms, Data Structures and Computational Complexity Keyword: largest common subgraph, subgraph isomorphism, almost trees, NP-complete,
	Summary \| Full Text:PDF