Toshihiro Fujito

J-GLOBAL         Last updated: Nov 1, 2019 at 14:29
Toshihiro Fujito
Toyohashi University of Technology

Research Areas


Awards & Honors

Editors' choice, 1998 edition, Discrete Applied Mathematics

Published Papers

Toshihiro Fujito, Kei Kimura,Yuki Mizuno
WALCOM: Algorithms and Computation - 12th International Conference, WALCOM 2018, Dhaka, Bangladesh, March 3-5, 2018, Proceedings   32-43   2018   [Refereed]
On Approximability of Connected Path Vertex Cover
Toshihiro Fujito
15th Workshop on Approximation and Online Algorithms   17-25   2018   [Refereed]
The Fewest Clues Problem of Picross 3D
Kei Kimura, Takuya Kamenashi, Toshihiro Fujito
9th International Conference on Fun with Algorithms      2018   [Refereed]
Toshihiro Fujito, Tomoaki Shimoda
Theory of Computing Systems   1-24   Apr 2017
© 2017 Springer Science+Business Media New York The edge dominating set problem (EDS) is to compute a minimum size edge set such that every edge is dominated by some edge in it. This paper considers a variant of EDS with extensions of multiple and...
Toshihiro Fujito
Algorithms and Complexity - 10th International Conference, CIAC 2017, Athens, Greece, May 24-26, 2017, Proceedings   10236 LNCS 234-246   Jan 2017   [Refereed]
© Springer International Publishing AG 2017. The Bounded Degree Deletion problem with degree bound b: V ¨ Z+ (denoted b-BDD), is that of computing a minimum cost vertex set in a graph G = (V,E) such that, when it is removed from G, the degree of a...
Hiroshi Fujiwara,Takahiro Seki,Toshihiro Fujito
IEICE Transactions   E99.D(3) 574-574   Mar 2016   [Refereed]
Tomoya Hibi,Toshihiro Fujito
Algorithmica   74(2) 778-786   Feb 2016   [Refereed]
Toshihiro Fujito,Daichi Suzuki
WALCOM: Algorithms and Computation - 10th International Workshop, WALCOM 2016, Kathmandu, Nepal, March 29-31, 2016, Proceedings   9627 251-262   2016   [Refereed]
Toshihiro Fujito,Tomoaki Shimoda
Computer Science - Theory and Applications - 11th International Computer Science Symposium in Russia, CSR 2016, St. Petersburg, Russia, June 9-13, 2016, Proceedings   9691 161-176   2016   [Refereed]
Hiroshi Fujiwara,Takuma Kitano,Toshihiro Fujito
J. Comb. Optim.   31(2) 463-490   2016   [Refereed]
Hiroshi Fujiwara,Shunsuke Satou,Toshihiro Fujito
IEICE Transactions   E99.A(6) 1083-1083   2016   [Refereed]
Hiroshi Fujiwara,Atsushi Matsuda,Toshihiro Fujito
IEICE Transactions   E99.D(3) 566-566   2016   [Refereed]
Hiroshi Fujiwara,Takuya Nakamura,Toshihiro Fujito
IEICE Transactions   E98.A(6) 1189-1196   Jun 2015   [Refereed]
Hisashi Araki,Toshihiro Fujito,Shota Inoue
IEICE Transactions   E98.A(6) 1153-1160   2015   [Refereed]
Hiroshi Fujiwara,Yasuhiro Konno,Toshihiro Fujito
IEICE Transactions   E97.A(6) 1200-1205   Jun 2014   [Refereed]
Toshihiro Fujito
Algorithm Theory - SWAT 2014 - 14th Scandinavian Symposium and Workshops, Copenhagen, Denmark, July 2-4, 2014. Proceedings   8503 206-216   2014   [Refereed]
Hiroshi Fujiwara,Takahiro Seki,Toshihiro Fujito
Discrete and Computational Geometry and Graphs - 16th Japanese Conference, JCDCGG 2013, Tokyo, Japan, September 17-19, 2013, Revised Selected Papers   8845 65-76   2013   [Refereed]
Toshihiro Fujito,Takayoshi Sakamaki
Inf. Process. Lett.   113(19-21) 844-847   2013   [Refereed]
Tomoya Hibi,Toshihiro Fujito
Graph-Theoretic Concepts in Computer Science - 38th International Workshop, WG 2012, Jerusalem, Israel, June 26-28, 2012, Revised Selcted Papers   7551 LNCS 215-224   2012   [Refereed]
Toshihiro Fujito,Takayoshi Sakamaki
Eighteenth Computing: The Australasian Theory Symposium, CATS 2012, Melbourne, Australia, January 2012   93-96   2012   [Refereed]
Toshihiro Fujito
ACM Transactions on Algorithms   8(2) 16   2012   [Refereed]
Hiroshi Fujiwara,Takuma Kitano,Toshihiro Fujito
Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Yokohama, Japan, December 5-8, 2011. Proceedings   7074 544-553   2011   [Refereed]
Fujito Toshihiro
Toshihiro Fujito
IEICE Transactions   92-A(8) 1749   2009   [Refereed]
Takashi Doi,Toshihiro Fujito
Discrete Optimization   3(3) 230-237   Sep 2006   [Refereed]
Toshihiro Fujito
Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I   431-442   2006   [Refereed]
Toshihiro Fujito,Tsuyoshi Okumura
Discrete Applied Mathematics   154(9) 1392-1400   2006   [Refereed]
Toshihiro Fujito, Takatoshi Yabuta
Lecture Notes in Computer Science   3351 154-166   Sep 2005   [Refereed]
Suppose there are a set of suppliers i and a set of consumers j with demands b j , and the amount of products that can be shipped from i to j is at most c ij . The amount of products that a supplier i can produce is an integer multiple of its ca...
Toshihiro Fujito,Hidekazu Kurahashi
Approximation and Online Algorithms, Third International Workshop, WAOA 2005, Palma de Mallorca, Spain, October 6-7, 2005, Revised Papers   176-189   2005   [Refereed]
電子情報通信学会論文誌 D-1   J87-D-1(11) 953-960   Nov 2004   [Refereed]
Toshihiro Fujito,Takatoshi Yabuta
Approximation and Online Algorithms, Second International Workshop, WAOA 2004, Bergen, Norway, September 14-16, 2004, Revised Selected Papers   154-166   2004   [Refereed]
Toshihiro Fujito
J. Comb. Optim.   8(4) 439-452   2004   [Refereed]
Toshihiro Fujito,Takashi Doi
Inf. Process. Lett.   90(2) 59-63   2004   [Refereed]
Takashi Doi,Toshihiro Fujito
Electronic Notes in Discrete Mathematics   17 135-140   2004   [Refereed]
Toshihiro Fujito
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences   E85-A 1066-1070   Jan 2002   [Refereed]
We consider the polymatroid packing and covering problems. The polynomial time algorithm with the best approximation bound known for either problem is the greedy algorithm, yielding guaranteed approximation factors of 1/k for polymatroid packing a...
Toshihiro Fujito,Hiroshi Nagamochi
Discrete Applied Mathematics   118(3) 199-207   2002   [Refereed]
Toshihiro Fujito,Tsuyoshi Okumura
Algorithms and Computation, 12th International Symposium, ISAAC 2001, Christchurch, New Zealand, December 19-21, 2001, Proceedings   670-681   2001   [Refereed]
Robert D. Carr,Toshihiro Fujito,Goran Konjevod,Ojas Parekh
J. Comb. Optim.   5(3) 317-326   2001   [Refereed]
Toshihiro Fujito
Inf. Process. Lett.   79(6) 261-266   2001   [Refereed]
Toshihiro Fujito
IEICE Transactions on Information and Systems   E83-D 480-487   Mar 2000   [Refereed][Invited]
SUMMARY The main problem considered is submodular set cover the problem of minimizing a linear function under a nondecreasing submodular constraint which generalizes both wellknown set cover and minimum matroid base problems. The problem is JVP-ha...
Toshihiro Fujito, Toshihiro Fujito, Satoshi Taoka, Satoshi Taoka, Toshimasa Watanabe, Toshimasa Watanabe
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences   E83-A 480-485   Jan 2000   [Refereed]
The legal firing sequence problem (LFS) asks if it is possible to fire each transition some prescribed number of times in a given Petri net. It is a fundamental problem in Petri net theory as it appears as a subproblem, or as a simplified version ...
Robert D. Carr,Toshihiro Fujito,Goran Konjevod,Ojas Parekh
Algorithms - ESA 2000, 8th Annual European Symposium, Saarbrücken, Germany, September 5-8, 2000, Proceedings   1879 132-142   Jan 2000   [Refereed]
© Springer-Verlag Berlin Heidelberg 2000. We study the approximability of the weighted edge-dominating set problem. Although even the unweighted case is JVP-Complete, in this case a solution of size at most twice the minimum can be efficiently com...
Toshihiro Fujito
Theor. Comput. Sci.   246(1-2) 107-116   2000   [Refereed]
Toshihiro Fujito
Foundations of Software Technology and Theoretical Computer Science, 20th Conference, FST TCS 2000 New Delhi, India, December 13-15, 2000, Proceedings.   117-126   2000   [Refereed]
Vineet Bafna,Piotr Berman,Toshihiro Fujito
SIAM J. Discrete Math.   12(3) 289-297   1999   [Refereed]
Toshihiro Fujito
Oper. Res. Lett.   25(4) 169-174   1999   [Refereed]
Piotr Berman,Toshihiro Fujito
Theory Comput. Syst.   32(2) 115-132   1999   [Refereed]
Toshihiro Fujito
J. Algorithms   31(1) 211-227   1999   [Refereed]
Toshihiro Fujito
Discrete Applied Mathematics   86(2-3) 213-231   1998   [Refereed]
Toshihiro Fujito
Automata, Languages and Programming, 24th International Colloquium, ICALP'97, Bologna, Italy, 7-11 July 1997, Proceedings   749-759   1997   [Refereed]
Toshihiro Fujito
Algorithms - ESA '96, Fourth Annual European Symposium, Barcelona, Spain, September 25-27, 1996, Proceedings   167-178   1996   [Refereed]
Toshihiro Fujito
Inf. Process. Lett.   59(2) 59-63   1996   [Refereed]
Piotr Berman,Toshihiro Fujito
Algorithms and Data Structures, 4th International Workshop, WADS '95, Kingston, Ontario, Canada, August 16-18, 1995, Proceedings   449-460   1995   [Refereed]
Vineet Bafna,Piotr Berman,Toshihiro Fujito
Algorithms and Computation, 6th International Symposium, ISAAC '95, Cairns, Australia, December 4-6, 1995, Proceedings   142-151   1995   [Refereed]
Toshihiro Fujito
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   762 LNCS 185-190   Jan 1993   [Refereed]
© Springer-Verlag Berlin Heidelberg 1993. The computational complexity of the matroid matching problem, which generalizes the matching problem in general graphs and the matroid intersection problem, remains unresolved. Under the general assumption...
Kenjiro Komai, Kohji Minoshima, Toshihiro Fujito
Transactions of the Japan Institute of Metals   27(1) 23-31   Jan 1986   [Refereed]
The stress corrosion cracking (SCC) initiation behavior under a sustained load with small vibratory loads superimposed has been investigated on high-strength low-alloy steel AISI 4135 sensitive to hydrogen embrittlement (HE)-type SCC immersed in 3...
駒井謙治郎, みの島弘二, 藤戸敏弘
日本金属学会誌   48(3) 307-313   Mar 1984


電子情報通信学会技術研究報告   112(498(COMP2012 52-62)) 1-4   Mar 2013
Hiroshi Fujiwara, Yasuhiro Konno, Toshihiro Fujito
IET Conference Publications   2013 24-29   Jan 2013
The multislope ski-rental problem is an extension of the classical ski-rental problem, where the player has several options of paying both of a per-time fee and an initial fee, in addition to pure renting and buying options. Damaschke gave a lower...
Hiroshi Fujiwara, Yasuhiro Konno, Toshihiro Fujito
11th International Symposium on Operations Research and its Applications in Engineering, Technology and Management 2013, ISORA 2013   1-6   Jan 2013
The multislope ski-rental problem is an extension of the classical ski-rental problem, where the player has several options of paying both of a per-time fee and an initial fee, in addition to pure renting and buying options. Damaschke gave a lower...
SAKAMAKI Takayoshi, FUJITO Toshihiro
IEICE technical report. Theoretical foundations of Computing   111(360) 33-36   Dec 2011
This paper shows that the optimization problem arising from the guarding game played between the cop and robber players on an undirected graph, can be approximated within a factor of Θ(log n) when the robber region is a tree.
北野 琢麻, 藤原 洋志, 藤戸 敏弘
研究報告アルゴリズム(AL)   2011(6) 1-8   Jan 2011
古典的スキーレンタル問題 11) を一般化した多状態スキーレンタル問題 12) について研究する.プレーヤーにはレンタルか購入の選択肢に加え,初期費用と単位時間毎の両方の料金を支払う選択肢が与えられる.我々は,与えられたインスタンスに対し達成可能な最適戦略の競合比を最適競合比として定義する.そして任意のインスタンスに対し,最適競合比の上限と下限を解析する.下限はプレーヤーにとって最も有利なインスタンスが選ばれたとき,どれだけ良い競合比が達成可能かを示す.一方,上限はいわゆる競合比についての...
電子情報通信学会技術研究報告   109(465(COMP2009 49-58)) 33-38   Mar 2010
The independent set problem in graphs is such an NP-hard problem that is known to be hard even to approximate effectively in polynomial time. When graphs are restricted to be d-claw free, while the standard local search heuristic can approximate i...
Toshihiro Fujito
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences   E92-A 1749   Jan 2009
Fujito Toshihiro
IPSJ SIG Notes   2006(71) 13-20   Jul 2006
The minimum cost tree cover problem is to compute a minimum cost tree T in a given connected graph G with costs on the edges, such that the vertices of T form a vertex cover for G. The problem is supposed to arise in applications of vertex cover a...
電子情報通信学会技術研究報告   104(642(COMP2004 60-72)) 9-16   Jan 2005
The set multicover problem is a well known NP-hard combinatorial optimization. Given a family of subsets of a base set U and coverage requirements r_u for each u ⋴ U, this problem is the one of finding a minimum size subfamily C such that ev...
電子情報通信学会技術研究報告   104(642(COMP2004 60-72)) 17-22   Jan 2005
Given a collection of weighted sets, the weighted set packing problem is to find a collection of mutually disjoint sets of maximum total weight. In particular, if each set contains at most k elements, we call the probelem k-set packing problem (k-...
電子情報通信学会技術研究報告   102(593(COMP2002 62-73)) 13-19   Jan 2003
電子情報通信学会技術研究報告   102(593(COMP2002 62-73)) 9-12   Jan 2003
DOI Takashi, FUJITO Toshihiro
IEICE technical report. Theoretical foundations of Computing   102(593) 9-12   Jan 2003
The connected vertex cover problem and the tree cover problem are respectively the vertex cover problem and the edge dominating set problem with additional requirement of connectivity attached to them. They are known to be NP-complete problems and...
YABUTA Takatoshi, FUJITO Toshihiro
IEICE technical report. Theoretical foundations of Computing   102(593) 13-19   Jan 2003
The vertex cover problem is a well known NP-hard combinatorial optimization. Given an undirected graph G = (V, E), a vertex cover of G is set C⫅V such that for every e ⋴ E, there exists ν ∈ e ∩ C. The vertex cover problem is the problem...
電子情報通信学会技術研究報告   102(90(COMP2002 9-14)) 41-48   May 2002
OKUMURA Tsuyoshi, FUJITO Toshihiro
IEICE technical report. Theoretical foundations of Computing   102(90) 41-48   May 2002
The set cover problem is an optimization problem that models many resource selection problems. Given a base set U and a family of weighted subsets of U , the problem is to find a minimum weight subfamily such that each element of U belongs to at l...
Fujito Toshihiro, Okumura Tsuyoshi
IEICE technical report. Theoretical foundations of Computing   101(184) 17-24   Jul 2001
The set cover problem is that of computing, given a family of weighted subsets of a base set U, a minimum weight subfamily F′ such that every element of U is covered by some subset in F′. The κ-set cover problem is a variant in which every subset ...
新しいパラダイムとしてのアルゴリズム工学:計算困難問題への挑戦 平成10-12年度 No.703   153-161   2001
Fujito Toshihiro
IEICE technical report. Theoretical foundations of Computing   100(144) 9-16   Jun 2000
We investigate polynomial-time approximability of the problems related to edge dominating sets of graphs. When edges are uniformly weighted, approximating the edge dominating set problem is polynomially equivalent to approximating the minimum maxi...
Fujito Toshihiro, Nagamochi Hiroshi
IEICE technical report. Theoretical foundations of Computing   99(724) 57-63   Mar 2000
We present a polynomial time algorithm approximating the minimum weight edge domi-nating set problem within a factor of 2. It has been known that the problem is NP-hard but, when edge weights are uniform (so that the smaller the better), it can be...
Fujito Toshihiro
RIMS Kokyuroku   1120 174-181   Dec 1999
情報処理学会研究報告   99(15(MPS-23)) 13-18   Feb 1999
A hypergraph consists of a vertex set and a family of its subsets. Although hypergraph problems are a generalization of graph problems, it seems that research results on approximation algorithms for hypergraph problems are much less than those for...
電子情報通信学会技術研究報告   98(565(CST98 29-38)) 23-30   Jan 1999
The Legal Firing Sequence problem of Petri nets(LFS for short)is defined by "Given a Petri net N, an initial marking M and a firing count vector X, find a firing sequence σ, starting from M, such that each transition t appears in σ exactly X(t)tim...
Fujito Toshihiro
IEICE technical report. Theoretical foundations of Computing   98(283) 25-31   Sep 1998
We design a primal-dual heuristic for the submodular set cover problem and analyze its performance giving an approximation bound as a generalization of the one for the set cover problem. It will be shown as an application that a capacitated versio...
IPSJ SIG Notes   97(8) 37-44   Jan 1997
This paper is concerned with polynomial time approximability of node-deletion problems for hereditary properties. It has been known that when such a property has only a finite number of minimal forbidden graphs the corresponding node-deletion prob...
Toshihiro Fujito
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   1256 749-759   Jan 1997
© Springer-Verlag Berlin Heidelberg 1997. This paper is concerned with the polynomial time approximability of node-deletion problems for hereditary properties. We will focus on such graph properties that axe derived from matroids definable on the ...
Shibata Isao, Fujito Toshihiro, Watanabe Toshimasa
IPSJ SIG Notes   95(109) 1-8   Nov 1995
The subject of paper is the vertex cover problem (VCP) and the connected vertex cover problem (CVCP) for 3-connected graphs. More specifically, VCP and CVCP for the two classes of 3-connected graphs, called quasi-wheels and super-wheels, are consi...
Toshihiro Fujito
Algorithms and Computation, 4th International Symposium, ISAAC '93, Hong Kong, December 15-17, 1993, Proceedings   185-190   1993   [Refereed]
情報処理学会全国大会講演論文集   35th(2) 1035-1036   1987