Keyword : NP-completeness


Program File Placement Problem for Machine-to-Machine Service Network Platform
Takehiro SATO Eiji OKI 
Publication:   
Publication Date: 2019/03/01
Vol. E102-B  No. 3 ; pp. 418-428
Type of Manuscript:  Special Section PAPER (Special Section on Network Virtualization and Network Softwarization for Diverse 5G Services)
Category: 
Keyword: 
IoTM2Mplacement problemoptimizationNP-completenessheuristic algorithm
 Summary | Full Text:PDF(1.8MB)

An Efficient Pattern Matching Algorithm for Unordered Term Tree Patterns of Bounded Dimension
Takayoshi SHOUDAI Tetsuhiro MIYAHARA Tomoyuki UCHIDA Satoshi MATSUMOTO Yusuke SUZUKI 
Publication:   
Publication Date: 2018/09/01
Vol. E101-A  No. 9 ; pp. 1344-1354
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
tree structured patterngraph pattern matching algorithmpolynomial time algorithmNP-completeness
 Summary | Full Text:PDF(2MB)

An Exact Algorithm for Lowest Edge Dominating Set
Ken IWAIDE Hiroshi NAGAMOCHI 
Publication:   
Publication Date: 2017/03/01
Vol. E100-D  No. 3 ; pp. 414-421
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science — New Trends in Theoretical Computer Science —)
Category: 
Keyword: 
graph theoryedge dominating setalgorithmNP-completenessfixed parameter tractable
 Summary | Full Text:PDF(304.7KB)

An Efficient Pattern Matching Algorithm for Ordered Term Tree Patterns
Yusuke SUZUKI Takayoshi SHOUDAI Tomoyuki UCHIDA Tetsuhiro MIYAHARA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2015/06/01
Vol. E98-A  No. 6 ; pp. 1197-1211
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
ordered tree structured patterngraph pattern matching algorithmpolynomial time algorithmNP-completeness
 Summary | Full Text:PDF(2MB)

Computational Complexity of Generalized Golf Solitaire
Chuzo IWAMOTO 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2015/03/01
Vol. E98-D  No. 3 ; pp. 541-544
Type of Manuscript:  Special Section LETTER (Special Section on Foundations of Computer Science---New Spirits in Theory of Computation and Algorithm---)
Category: 
Keyword: 
computational complexityNP-completenesspuzzle
 Summary | Full Text:PDF(372.2KB)

Computational Complexity of Generalized Forty Thieves
Chuzo IWAMOTO Yuta MATSUI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2015/02/01
Vol. E98-D  No. 2 ; pp. 429-432
Type of Manuscript:  LETTER
Category: Fundamentals of Information Systems
Keyword: 
computational complexityNP-completenesspuzzle
 Summary | Full Text:PDF(385KB)

Computational Complexity and an Integer Programming Model of Shakashaka
Erik D. DEMAINE Yoshio OKAMOTO Ryuhei UEHARA Yushi UNO 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2014/06/01
Vol. E97-A  No. 6 ; pp. 1213-1219
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
integer programmingNP-completenesspencil-and-paper puzzleShakashaka
 Summary | Full Text:PDF(1.5MB)

BLOCKSUM is NP-Complete
Kazuya HARAGUCHI Hirotaka ONO 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2013/03/01
Vol. E96-D  No. 3 ; pp. 481-488
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science — New Trends in Algorithms and Theory of Computation —)
Category: 
Keyword: 
NP-completenesscombinatorial puzzleLatin squareBLOCKSUM
 Summary | Full Text:PDF(1003.6KB)

Complexity and a Heuristic Algorithm of Computing Parallel Degree for Program Nets with SWITCH-Nodes
Shingo YAMAGUCHI Tomohiro TAKAI Tatsuya WATANABE Qi-Wei GE Minoru TANAKA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2006/11/01
Vol. E89-A  No. 11 ; pp. 3207-3215
Type of Manuscript:  Special Section PAPER (Special Section on Concurrent/Hybrid Systems: Theory and Applications)
Category: Concurrent Systems
Keyword: 
program netsparallel degreecomputation complexityNP-completeness
 Summary | Full Text:PDF(428.7KB)

Dead Problem of Program Nets
Shingo YAMAGUCHI Kousuke YAMADA Qi-Wei GE Minoru TANAKA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2006/04/01
Vol. E89-A  No. 4 ; pp. 887-894
Type of Manuscript:  Special Section PAPER (Special Section on Selected Papers from the 18th Workshop on Circuits and Systems in Karuizawa)
Category: 
Keyword: 
program netsdeaddead problemcomputation complexityNP-completeness
 Summary | Full Text:PDF(388.7KB)

A Note on the Complexity of Scheduling for Precedence Constrained Messages in Distributed Systems
Koji GODA Toshinori YAMADA Shuichi UENO 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2005/04/01
Vol. E88-A  No. 4 ; pp. 1090-1092
Type of Manuscript:  LETTER
Category: Algorithms and Data Structures
Keyword: 
schedulingNP-completenessapproximation algorithm
 Summary | Full Text:PDF(69.6KB)

Database Allocation Modeling for Optimal Design of Distributed Systems
Jae-Woo LEE Doo-Kwon BAIK 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2004/07/01
Vol. E87-D  No. 7 ; pp. 1795-1804
Type of Manuscript:  Special Section PAPER (Special Section on Hardware/Software Support for High Performance Scientific and Engineering Computing)
Category: Distributed, Grid and P2P Computing
Keyword: 
distributed databasefragment replicationheuristic algorithmfile allocation modelNP-completeness
 Summary | Full Text:PDF(226.9KB)

-Coloring Problem
Akihiro UEJIMA Hiro ITO Tatsuie TSUKIJI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2004/05/01
Vol. E87-A  No. 5 ; pp. 1243-1250
Type of Manuscript:  PAPER
Category: Graphs and Networks
Keyword: 
H-coloringcycles of odd ordercomplement graphsNP-completeness
 Summary | Full Text:PDF(593.7KB)

On Group Multicast Routing with Bandwidth Constraint: A Lower Bound and Performance Evaluation
Chor Ping LOW Ning WANG 
Publication:   IEICE TRANSACTIONS on Communications
Publication Date: 2004/01/01
Vol. E87-B  No. 1 ; pp. 124-131
Type of Manuscript:  PAPER
Category: Network
Keyword: 
multicast routingheuristic algorithmlower bound techniquesNP-completeness
 Summary | Full Text:PDF(946.2KB)

Scheduling Task In-Trees on Distributed Memory Systems
Sanjeev BASKIYAR 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2001/06/01
Vol. E84-D  No. 6 ; pp. 685-691
Type of Manuscript:  PAPER
Category: Theory and Models of Software
Keyword: 
schedulingNP-completenesstask-treemakespanmultiprocessorsinterprocessor communication
 Summary | Full Text:PDF(288KB)

Time Complexity Analysis of the Minimal Siphon Extraction Problem of Petri Nets
Masahiro YAMAUCHI Toshimasa WATANABE 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1999/11/25
Vol. E82-A  No. 11 ; pp. 2558-2565
Type of Manuscript:  Special Section PAPER (Special Section on Concurrent Systems Technology)
Category: 
Keyword: 
Petri netminimal siphonspolynomial time solvabilityNP-completenessstrongly connectedness
 Summary | Full Text:PDF(585.6KB)

Finding a Minimal Siphon Containing Specified Places in a General Petri Net
Masahiro YAMAUCHI Shinji TANIMOTO Toshimasa WATANABE 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1996/11/25
Vol. E79-A  No. 11 ; pp. 1825-1828
Type of Manuscript:  Special Section LETTER (Special Section on Description Models for Concurrent Systems and Their Applications)
Category: 
Keyword: 
general Petri netsminimal siphonspolynomial-time algorithmsstrongly connectedneddNP-completeness
 Summary | Full Text:PDF(334.6KB)

Finding Minimal Siphons in General Petri Nets
Shinji TANIMOTO Masahiro YAMAUCHI Toshimasa WATANABE 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1996/11/25
Vol. E79-A  No. 11 ; pp. 1817-1824
Type of Manuscript:  Special Section PAPER (Special Section on Description Models for Concurrent Systems and Their Applications)
Category: 
Keyword: 
general Petri netsminimal siphonspolynomial-time algorithmsstrongly connectednessNP-completeness
 Summary | Full Text:PDF(616.4KB)

On the Complexity of Embedding of Graphs into Grids with Minimum Congestion
Akira MATSUBAYASHI Shuichi UENO 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1996/04/25
Vol. E79-A  No. 4 ; pp. 469-476
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
NP-completenessgraph embeddingcongestiongridVLSI layout
 Summary | Full Text:PDF(652.5KB)

Is a Given Flow Uncontrollable?
Tomomi MATSUI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1996/04/25
Vol. E79-A  No. 4 ; pp. 448-451
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
network flowNP-completeness
 Summary | Full Text:PDF(301.4KB)