IEICE Trans

Keyword : NP-completeness

Stronger Hardness Results on the Computational Complexity of Picross 3D Kei KIMURA
Publication: Publication Date: 2020/04/01 Vol. E103-A No. 4 ; pp. 668-676 Type of Manuscript: PAPER Category: Algorithms and Data Structures Keyword: computational complexity, puzzle, Picross 3D, NP-completeness, #P-completeness, Σ^P₂-completeness,
	Summary \| Full Text:PDF(688.3KB)

NP-Completeness of Fill-a-Pix and Σ^P₂-Completeness of Its Fewest Clues Problem Yuta HIGUCHI Kei KIMURA
Publication: Publication Date: 2019/11/01 Vol. E102-A No. 11 ; pp. 1490-1496 Type of Manuscript: PAPER Category: Algorithms and Data Structures Keyword: computational complexity, pencil-and-paper puzzle, Fill-a-Pix, NP-completeness, Σ^P₂-completeness,
	Summary \| Full Text:PDF(1.2MB)

On Computational Complexity of Pipe Puzzles Takumu SHIRAYAMA Takuto SHIGEMURA Yota OTACHI Shuichi MIYAZAKI Ryuhei UEHARA
Publication: Publication Date: 2019/09/01 Vol. E102-A No. 9 ; pp. 1134-1141 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Puzzles Keyword: pipe puzzle, NP-completeness, polynomial-time algorithm,
	Summary \| Full Text:PDF(7MB)

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: IoT, M2M, placement problem, optimization, NP-completeness, heuristic 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 pattern, graph pattern matching algorithm, polynomial time algorithm, NP-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 theory, edge dominating set, algorithm, NP-completeness, fixed 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 pattern, graph pattern matching algorithm, polynomial time algorithm, NP-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 complexity, NP-completeness, puzzle,
	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 complexity, NP-completeness, puzzle,
	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 programming, NP-completeness, pencil-and-paper puzzle, Shakashaka,
	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-completeness, combinatorial puzzle, Latin square, BLOCKSUM,
	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 nets, parallel degree, computation complexity, NP-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 nets, dead, dead problem, computation complexity, NP-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: scheduling, NP-completeness, approximation 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 database, fragment replication, heuristic algorithm, file allocation model, NP-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-coloring, cycles of odd order, complement graphs, NP-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 routing, heuristic algorithm, lower bound techniques, NP-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: scheduling, NP-completeness, task-tree, makespan, multiprocessors, interprocessor 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 net, minimal siphons, polynomial time solvability, NP-completeness, strongly connectedness,
	Summary \| Full Text:PDF(585.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 nets, minimal siphons, polynomial-time algorithms, strongly connectedness, NP-completeness,
	Summary \| Full Text:PDF(616.4KB)

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 nets, minimal siphons, polynomial-time algorithms, strongly connectednedd, NP-completeness,
	Summary \| Full Text:PDF(334.6KB)

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-completeness, graph embedding, congestion, grid, VLSI 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 flow, NP-completeness,
	Summary \| Full Text:PDF(301.4KB)