| 2023 | CIAC | Approximating Power Node-Deletion Problems. | Toshihiro Fujito, Kneto Mukae, Junya Tsuzuki |
| 2021 | WAOA | On b-Matchings and b-Edge Dominating Sets: A 2-Approximation Algorithm for the 4-Edge Dominating Set Problem. | Toshihiro Fujito, Takumi Tatematsu |
| 2020 | TAMC | Eternal Connected Vertex Cover Problem. | Toshihiro Fujito, Tomoya Nakamura |
| 2018 | FUN | The Fewest Clues Problem of Picross 3D. | Kei Kimura, Takuya Kamehashi, Toshihiro Fujito |
| 2018 | WALCOM | Approximating Partially Bounded Degree Deletion on Directed Graphs. | Toshihiro Fujito, Kei Kimura, Yuki Mizuno |
| 2017 | CIAC | Approximating Bounded Degree Deletion via Matroid Matching. | Toshihiro Fujito |
| 2017 | WAOA | On Approximability of Connected Path Vertex Cover. | Toshihiro Fujito |
| 2016 | CSR | On Approximating (Connected) 2-Edge Dominating Set by a Tree. | Toshihiro Fujito, Tomoaki Shimoda |
| 2016 | WALCOM | Fast and Simple Local Algorithms for 2-Edge Dominating Sets and 3-Total Vertex Covers. | Toshihiro Fujito, Daichi Suzuki |
| 2012 | WG | Multi-rooted Greedy Approximation of Directed Steiner Trees with Applications. | Tomoya Hibi, Toshihiro Fujito |
| 2011 | ISAAC | On the Best Possible Competitive Ratio for Multislope Ski Rental. | Hiroshi Fujiwara, Takuma Kitano, Toshihiro Fujito |
| 2006 | ICALP | How to Trim an MST: A 2-Approximation Algorithm for Minimum Cost Tree Cover. | Toshihiro Fujito |
| 2005 | WAOA | A Better-Than-Greedy Algorithm for | Toshihiro Fujito, Hidekazu Kurahashi |
| 2004 | WAOA | Submodular Integer Cover and Its Application to Production Planning. | Toshihiro Fujito, Takatoshi Yabuta |
| 2001 | ISAAC | A Modified Greedy Algorithm for the Set Cover Problem with Weights 1 and 2. | Toshihiro Fujito, Tsuyoshi Okumura |
| 2000 | ESA | A 2 1/10-Approximation Algorithm for a Generalization of the Weighted Edge-Dominating Set Problem. | Robert D. Carr, Toshihiro Fujito, Goran Konjevod, Ojas Parekh |
| 1997 | ICALP | A Primal-Dual Approach to Approximation of Node-Deletion Problems for Matroidal Properties. | Toshihiro Fujito |
| 1996 | ESA | A Unified Local Ratio Approximation of Node-Deletion Problems (Extended Abstract). | Toshihiro Fujito |
| 1995 | ISAAC | Constant Ratio Approximations of the Weighted Feedback Vertex Set Problem for Undirected Graphs. | Vineet Bafna, Piotr Berman, Toshihiro Fujito |
| 1995 | WADS | On the Approximation Properties of Independent Set Problem in Degree 3 Graphs. | Piotr Berman, Toshihiro Fujito |
| 1993 | ISAAC | A 2or3-Approximation of the Matroid Matching Problem. | Toshihiro Fujito |