Keyword : NP-hard


Visibility Problems for Manhattan Towers
Chuzo IWAMOTO Yusuke KITAGAKI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2016/03/01
Vol. E99-D  No. 3 ; pp. 607-614
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science---Developments of the Theory of Algorithms and Computation---)
Category: 
Keyword: 
guarding problemManhattan towersNP-hard
 Summary | Full Text:PDF(582.8KB)

Maximizing the Total Weight of Just-In-Time Jobs under Multi-Slot Conditions Is NP-Hard
Eishi CHIBA Shinji IMAHORI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2016/02/01
Vol. E99-D  No. 2 ; pp. 525-528
Type of Manuscript:  LETTER
Category: Fundamentals of Information Systems
Keyword: 
schedulingjust-in-timetime slotweightNP-hard
 Summary | Full Text:PDF(130.1KB)

Finding the Minimum Number of Face Guards is NP-Hard
Chuzo IWAMOTO Yusuke KITAGAKI Kenichi MORITA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2012/11/01
Vol. E95-D  No. 11 ; pp. 2716-2719
Type of Manuscript:  LETTER
Category: Fundamentals of Information Systems
Keyword: 
face guardspolyhedral terrainsNP-hard
 Summary | Full Text:PDF(289.5KB)

An Algorithm for Minimum Feedback Vertex Set Problem on a Trapezoid Graph
Hirotoshi HONMA Yutaro KITAMURA Shigeru MASUYAMA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2011/06/01
Vol. E94-A  No. 6 ; pp. 1381-1385
Type of Manuscript:  Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
design and analysis of algorithmsfeedback vertex settrapezoid graphsNP-hard
 Summary | Full Text:PDF(168.3KB)

NP-Hard and k-EXPSPACE-Hard Cast Puzzles
Chuzo IWAMOTO Kento SASAKI Kenji NISHIO Kenichi MORITA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2010/11/01
Vol. E93-D  No. 11 ; pp. 2995-3004
Type of Manuscript:  PAPER
Category: Fundamentals of Information Systems
Keyword: 
computational complexityNP-hardk-EXPSPACE hardcast puzzle
 Summary | Full Text:PDF(645.8KB)

Inapproximability of the Minimum Biclique Edge Partition Problem
Hideaki OTSUKI Tomio HIRATA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2010/02/01
Vol. E93-D  No. 2 ; pp. 290-292
Type of Manuscript:  Special Section LETTER (Special Section on Foundations of Computer Science)
Category: 
Keyword: 
bicliqueedge partitionNP-hardinapproximability
 Summary | Full Text:PDF(154.7KB)

Detecting a Singleton Attractor in a Boolean Network Utilizing SAT Algorithms
Takeyuki TAMURA Tatsuya AKUTSU 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2009/02/01
Vol. E92-A  No. 2 ; pp. 493-501
Type of Manuscript:  PAPER
Category: Algorithms and Data Structures
Keyword: 
Boolean networksingleton attractorfixed pointSATNP-hard
 Summary | Full Text:PDF(304.7KB)

Maximum-Cover Source-Location Problems
Kenya SUGIHARA Hiro ITO 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2006/05/01
Vol. E89-A  No. 5 ; pp. 1370-1377
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
graphedge-connectivitylocation problempolynomial-time algorithmNP-hard
 Summary | Full Text:PDF(288.5KB)

Inapproximability of the Edge-Contraction Problem
Hideaki OTSUKI Tomio HIRATA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2006/05/01
Vol. E89-A  No. 5 ; pp. 1425-1427
Type of Manuscript:  Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
edge-contraction problemNP-hardapproximation algorithmapproximabilityconnected vertex cover problem
 Summary | Full Text:PDF(103.1KB)

Anycast Routing and Wavelength Assignment Problem on WDM Network
Der-Rong DIN 
Publication:   IEICE TRANSACTIONS on Communications
Publication Date: 2005/10/01
Vol. E88-B  No. 10 ; pp. 3941-3951
Type of Manuscript:  Special Section PAPER (Special Section on Next Generation Photonic Network Technologies)
Category: 
Keyword: 
anycastrouting and wavelength assignmentNP-hardWDMgenetic algorithm
 Summary | Full Text:PDF(2MB)

Wireless ATM Backbone Network Design Problem
Der-Rong DIN 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2005/07/01
Vol. E88-A  No. 7 ; pp. 1777-1785
Type of Manuscript:  Special Section PAPER (Special Section on Multi-dimensional Mobile Information Networks)
Category: Network
Keyword: 
wireless ATMheuristic algorithmgenetic algorithmNP-hardbackbone network
 Summary | Full Text:PDF(530.4KB)

Anycast Routing Problem on WDM Ring Network
Der-Rong DIN 
Publication:   IEICE TRANSACTIONS on Communications
Publication Date: 2005/04/01
Vol. E88-B  No. 4 ; pp. 1347-1354
Type of Manuscript:  Special Section PAPER (Special Section on Internet Technology V)
Category: 
Keyword: 
anycast routingNP-hardWDM ringheuristic algorithmsimulated annealing
 Summary | Full Text:PDF(905KB)

Solving Facility Layout Problem Using an Improved Genetic Algorithm
Rong-Long WANG Kozo OKAZAKI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2005/02/01
Vol. E88-A  No. 2 ; pp. 606-610
Type of Manuscript:  LETTER
Category: Numerical Analysis and Optimization
Keyword: 
facility layout problemquadratic assignment problemNP-hardgenetic algorithms
 Summary | Full Text:PDF(373.6KB)

Hybrid Method for Solving Dual-Homing Cell Assignment Problem on Two-Level Wireless ATM Network
Der-Rong DIN 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2004/07/01
Vol. E87-A  No. 7 ; pp. 1664-1671
Type of Manuscript:  Special Section PAPER (Special Section on Multi-dimensional Mobile Information Networks)
Category: Network Theory
Keyword: 
NP-hardwireless ATMcell assignmentdual-homingsimulated annealingheuristic algorithm
 Summary | Full Text:PDF(327KB)

On Approximation Algorithms for Coloring k-Colorable Graphs
Xuzhen XIE Takao ONO Tomio HIRATA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2003/05/01
Vol. E86-A  No. 5 ; pp. 1046-1051
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
graph coloringapproximation algorithmsNP-hardmaximum degree
 Summary | Full Text:PDF(227.3KB)

A Quasi-Solution State Evolution Algorithm for Channel Assignment Problems in Cellular Networks
Nobuo FUNABIKI Toru NAKANISHI Tokumi YOKOHIRA Shigeto TAJIMA Teruo HIGASHINO 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2002/05/01
Vol. E85-A  No. 5 ; pp. 977-987
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
CAPapproximation algorithmbenchmarkNP-hardcellular network
 Summary | Full Text:PDF(623.9KB)

NP-Hardness of Rotation Type Cell-Mazes
Shiro AOKI Hiro ITO Hideyuki UEHARA Mitsuo YOKOYAMA Tsuyoshi HORINOUCHI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2000/03/25
Vol. E83-A  No. 3 ; pp. 492-496
Type of Manuscript:  Special Section LETTER (Special Section of Selected Papers from the 12th Workshop on Circuits and Systems in Karuizawa)
Category: 
Keyword: 
puzzlemazecomputational complexityNP-hardpolynomial-time
 Summary | Full Text:PDF(472.6KB)