Keyword : NP-hardness


Computational Complexity of Piano-Hinged Dissections
Zachary ABEL Erik D. DEMAINE Martin L. DEMAINE Takashi HORIYAMA Ryuhei UEHARA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2014/06/01
Vol. E97-A  No. 6 ; pp. 1206-1212
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
GeoLoophinged dissectionIvan's HingeNP-hardnesspaper folding
 Summary | Full Text:PDF(2.3MB)

Inapproximability of Maximum r-Regular Induced Connected Subgraph Problems
Yuichi ASAHIRO Hiroshi ETO Eiji MIYANO 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2013/03/01
Vol. E96-D  No. 3 ; pp. 443-449
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science — New Trends in Algorithms and Theory of Computation —)
Category: 
Keyword: 
induced connected subgraphregularityNP-hardnessinapproximability
 Summary | Full Text:PDF(443.6KB)

The Legal Firing Sequence Problem of Petri Nets
Toshimasa WATANABE 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2000/03/25
Vol. E83-D  No. 3 ; pp. 397-406
Type of Manuscript:  INVITED SURVEY PAPER
Category: Graph Algorithms
Keyword: 
Petri netslegal firing sequence problemstime complexity analysisNP-hardnesspseudo-polynomial time algorithms
 Summary | Full Text:PDF(681.1KB)