Keyword : inapproximability


On the Minimum Caterpillar Problem in Digraphs
Taku OKADA Akira SUZUKI Takehiro ITO Xiao ZHOU 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2014/03/01
Vol. E97-A  No. 3 ; pp. 848-857
Type of Manuscript:  PAPER
Category: Algorithms and Data Structures
Keyword: 
bounded treewidth graphcaterpillardynamic programminggraph algorithminapproximability
 Summary | Full Text:PDF(1.1MB)

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)

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)

An Approximation Algorithm for the Task-Coalition Assignment Problem
Yoshihiro MURATA Yasunori ISHIHARA Minoru ITO 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2002/04/01
Vol. E85-D  No. 4 ; pp. 685-693
Type of Manuscript:  PAPER
Category: Algorithms
Keyword: 
agentapproximation algorithmtasksassignmentinapproximability
 Summary | Full Text:PDF(482KB)