Keyword : NP-complete


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: 
Usowanpencil puzzleNP-complete
 Summary | Full Text:PDF(428KB)

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 channelNP-completerouting algorithmSteiner tree
 Summary | Full Text:PDF(1.3MB)

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 puzzlepencil puzzleNP-complete
 Summary | Full Text:PDF(774.9KB)

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 networkaccess-point aggregationNP-completealgorithmenergy-savingIEEE 802.11n
 Summary | Full Text:PDF(1.6MB)

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-completecomputational complexityone-player gamepyramid
 Summary | Full Text:PDF(371.7KB)

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-completecomputational complexityone-player gameShisen-Sho
 Summary | Full Text:PDF(595.1KB)

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 servicebackbone networkoptimization problemNP-completeapproximation algorithm
 Summary | Full Text:PDF(2.6MB)

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 networkWDS clusteringgateway selectionNP-completeheuristic algorithmvariable depth search
 Summary | Full Text:PDF(582.8KB)

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: 
LTEresource allocationadmission controlrenegingNP-completedynamic programminggreedy
 Summary | Full Text:PDF(356.3KB)

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: 
LTESONvertex coloringNP-completepermutationrandomized algorithms
 Summary | Full Text:PDF(341.4KB)

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 allocationwireless mesh networkalgorithmindoor environmentNP-complete
 Summary | Full Text:PDF(411.2KB)

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-SATCNOT gatecomplete test setfault testingNP-completereversible circuitstuck-at faulttest vector
 Summary | Full Text:PDF(261.4KB)

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 systemsecret sharing schemeSteiner treeNP-completedistributed algorithm
 Summary | Full Text:PDF(385KB)

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 CircuitEuler circuitgraph theorycontiguous costNP-completeapproximation algorithm
 Summary | Full Text:PDF(250.7KB)

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: 
ICRPheuristic algorithmminimum dead spaceNP-completeIEEE 802.6DQDB
 Summary | Full Text:PDF(271KB)

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: 
FPGAcustom circuitgraph algorithmNP-completepartial evaluation
 Summary | Full Text:PDF(472.8KB)

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 multicastreal-time communicationmultihome networkheuristic algorithmNP-complete
 Summary | Full Text:PDF(260.9KB)

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-completegraphalgorithmFPGA
 Summary | Full Text:PDF(325.1KB)

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-completecustom circuitFPGAgraph algorithm
 Summary | Full Text:PDF(257.7KB)

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 complexityNP-completeanother solutionpuzzle
 Summary | Full Text:PDF(282.3KB)

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 routingheuristic algorithmsbandwidth constraintNP-complete
 Summary | Full Text:PDF(1.3MB)

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: 
reallocationcomputational complexityNP-completeSATsteiner tree problem
 Summary | Full Text:PDF(536.7KB)

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 subgraphisomorphicNP-completegreedy methoddiscrete descent methodsimulated annealing
 Summary | Full Text:PDF(396.2KB)

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 netfile transferSteiner treeNP-complete
 Summary | Full Text:PDF(99.4KB)

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: 
grapharea graphdiameterdistanceconnectivityNP-completepolynomial timealgorithm
 Summary | Full Text:PDF(821.4KB)

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: 
FPGAboard-level routingNP-completedigital neural networkgreedy algorithm
 Summary | Full Text:PDF(543.2KB)

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 problemnetwork flowsNP-completeoptimization problem
 Summary | Full Text:PDF(526.4KB)

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 networkdigital technologytotal coloringNP-completecombinatorial optimization
 Summary | Full Text:PDF(328KB)

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: 
crosstalkmultilayer channel routingneural networkdigital technologyNP-complete
 Summary | Full Text:PDF(748.1KB)

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 problemnetwork flowsNP-completeoptimization problem
 Summary | Full Text:PDF(514.6KB)

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: 
graphreallocationlinear-timeNP-complete
 Summary | Full Text:PDF(817KB)

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 networkoptimization problemNP-complete
 Summary | Full Text:PDF(431.7KB)

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 problemflow networkNP-completeoptimization problem
 Summary | Full Text:PDF(738.3KB)

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 networklink activationNP-completeneural networkparallel algorithm
 Summary | Full Text:PDF(625.7KB)

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: 
reallocationgraphlinear timeNP-complete
 Summary | Full Text:PDF(724.1KB)

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 diagramvariable orderingoptimal linear arrangementNP-completeBoolean function
 Summary | Full Text:PDF(924.5KB)

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 cliqueNP-completeneural networkalgorithmenergy-descent opimization
 Summary | Full Text:PDF(605.7KB)

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 drawingtree-structured diagramsNP-completeconstraints for tree drawing
 Summary | Full Text:PDF(562.4KB)

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 complexityalphabet indexinglocal search algorithmNP-completePLS-complete
 Summary | Full Text:PDF(568.3KB)

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 complexitydeadlockNP-completeprotocolprotocol validation
 Summary | Full Text:PDF(781.5KB)

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 subgraphsubgraph isomorphismalmost treesNP-complete
 Summary | Full Text:PDF(397.7KB)