Yuichi ASAHIRO


An Approximation Algorithm for the Maximum Induced Matching Problem on C5-Free Regular Graphs
Yuichi ASAHIRO Guohui LIN Zhilong LIU Eiji MIYANO 
Publication:   
Publication Date: 2019/09/01
Vol. E102-A  No. 9  pp. 1142-1149
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: Optimization
Keyword: 
induced matching problemC5-free regular graphapproximation algorithm
 Summary | Full Text:PDF

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