Keyword : NP-hardness


The Stable Roommates Problem with Unranked Entries
Hiroaki SUTO Aleksandar SHURBEVSKI Hiroshi NAGAMOCHI 
Publication:   
Publication Date: 2018/09/01
Vol. E101-A  No. 9 ; pp. 1412-1419
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
stable matchingindifferenceNP-hardnessexact exponential algorithm
 Summary | Full Text:PDF(1.1MB)

Pseudo Polynomial Time Algorithms for Optimal Longcut Route Selection
Yuichi SUDO Toshimitsu MASUZAWA Gen MOTOYOSHI Tutomu MURASE 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2015/03/01
Vol. E98-D  No. 3 ; pp. 607-616
Type of Manuscript:  PAPER
Category: Fundamentals of Information Systems
Keyword: 
longcut routeroute selectionNP-hardnesspseudo polynomial time algorithm
 Summary | Full Text:PDF(805.5KB)

Minimum Spanning Tree Problem with Label Selection
Akio FUJIYOSHI Masakazu SUZUKI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2011/02/01
Vol. E94-D  No. 2 ; pp. 233-239
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science -- Mathematical Foundations and Applications of Algorithms and Computer Science --)
Category: 
Keyword: 
minimum spanning tree problemNP-hardnessseries-parallel graphmathematical OCR
 Summary | Full Text:PDF(459.9KB)

Time Complexity Analysis of the Legal Firing Sequence Problem of Petri Nets with Inhibitor Arcs
Satoshi TAOKA Toshimasa WATANABE 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2006/11/01
Vol. E89-A  No. 11 ; pp. 3216-3226
Type of Manuscript:  Special Section PAPER (Special Section on Concurrent/Hybrid Systems: Theory and Applications)
Category: Concurrent Systems
Keyword: 
Petri netsinhibitor-arcslegal firing sequencespseudo-polynomial time algorithmsNP-hardness
 Summary | Full Text:PDF(446.4KB)

Complexity and a Method of Extracting a Database Schema over Semistructured Documents
Nobutaka SUZUKI Yoichirou SATO Michiyoshi HAYASE 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2002/06/01
Vol. E85-D  No. 6 ; pp. 940-949
Type of Manuscript:  PAPER
Category: Databases
Keyword: 
semistructured dataschema extraction problemapproximabilityNP-hardness
 Summary | Full Text:PDF(628.3KB)

Single Machine Scheduling to Minimize the Maximum Lateness with Both Specific and Generalized Due Dates
Keisuke TANAKA Milan VLACH 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1997/03/25
Vol. E80-A  No. 3 ; pp. 557-563
Type of Manuscript:  Special Section PAPER (Special Section of Selected Papers from the 9th Karuizawa Workshop on Circuits and Systems)
Category: 
Keyword: 
single machine schedulinglatenessNP-hardness
 Summary | Full Text:PDF(518.5KB)

The Minimum Initial Marking Problem for Scheduling in Timed Petri Nets
Toshimasa WATANABE Takenobu TANIDA Masahiro YAMAUCHI Kenji ONAGA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1992/10/25
Vol. E75-A  No. 10 ; pp. 1407-1421
Type of Manuscript:  Special Section PAPER (Special Section on Application of Petri Nets to Concurrent System Design)
Category: 
Keyword: 
timed Petri netsschedulingapproximation algorithmstime complexityNP-hardness
 Summary | Full Text:PDF(1.1MB)