Ishii Toshimasa

Faculty of Economics and Business　Modern Economics and Management　Management AnalysisProfessor
Last Updated :2026/04/14

■Researcher basic information

Degree

  • Master of Engineering, Kyoto University
  • Doctor of Informatics, Kyoto University

Researchmap personal page

Home Page URL

J-Global ID

Research Keyword

  • グラフ理論
  • 組合せ最適化
  • アルゴリズム
  • Graph Theory
  • Combinatorial Optimization
  • Algorithm

Research Field

  • Informatics, Information theory

Educational Organization

■Career

Career

  • Sep. 2016 - Present
    北海道大学 大学院経済学研究院, 教授
  • Apr. 2012 - Aug. 2016
    Hokkaido University, Graduate School of Economics and Business Administration, 准教授
  • Apr. 2006 - Mar. 2012
    Otaru University of Commerce, Faculty of Commerce, Department of Information and Management Science, 助教授 (2006年) 准教授 (2007年～)
  • Apr. 2000 - Mar. 2006
    Toyohashi University of Technology, Faculty of Engineering, 助手

Educational Background

  • Apr. 1999 - Mar. 2000, Kyoto University, Graduate School of Informatics, Department of Applied Mathematics and Physis, Japan
  • 2000, Kyoto University, Graduate School, Division of Information and Communication
  • Apr. 1995 - Mar. 1999, Kyoto University, Graduate School of Engineering, 数理工学専攻
  • Apr. 1991 - Mar. 1995, Kyoto University, Faculty of Engineering, 数理工学科, Japan
  • 1995, Kyoto University, Faculty of Engineering

■Research activity information

Awards

  • Oct. 2022, Best Paper Candidate (The 28th International Computing and Combinatorics Conference (COCOON 2022))　　　　　　　　　　　　　　　
    Toshimasa Ishii;Jun Kawahara;Kazuhisa Makino;Hirotaka Ono
  • Mar. 2016, 情報処理学会 山下記念研究賞　　　　　　　　　　　　　　　
    石井 利昌
  • Sep. 2015, FIT 船井ベストペーパー賞　　　　　　　　　　　　　　　
    石井 利昌;牧野 和久
  • Mar. 2007, 日本オペレーションズ・リサーチ学会, 文献賞奨励賞　　　　　　　　　　　　　　　
    石井 利昌

Papers

Other Activities and Achievements

  • Reallocation Problems with Minimum Completion Time.
    Toshimasa Ishii, Jun Kawahara, Kazuhisa Makino, Hirotaka Ono, CoRR, abs/2111.02579, 2021
  • (Total) Vector Domination for Graphs with Bounded Branchwidth
    ISHII TOSHIMASA, ONO HIROTAKA, UNO YUSHI, IEICE technical report. Theoretical foundations of Computing, 114, 80, 1, 8, 13 Jun. 2014
    Given a graph G = (V, E) of order n and an n-dimensional non-negative vector d = (d(1), d(2),..., d(n)), called demand vector, the vector domination (resp., total vector domination) is the problem of finding a minimum S c V such that every vertex v in V＼S (resp., in V) has at least d(v) neighbors in S. The (total) vector domination is a generalization of many dominating set type problems, e.g., the dominating set problem, the k-tuple dominating set problem (this k is different from the solution size), and so on, and its approximability and inapproximability have been studied under this general framework. In this paper, we show that a (total) vector domination of graphs with bounded branchwidth can be solved in polynomial time. This implies that the problem is polynomially solvable also for graphs with bounded treewidth. Consequently, the (total) vector domination problem for a planar graph is subexponential fixed-parameter tractable with respect to k, where k is the size of solution., The Institute of Electronics, Information and Communication Engineers, English
  • (Total) Vector Domination for Graphs with Bounded Branchwidth
    Toshimasa Ishii, Hirotaka Ono, Yushi Uno, IPSJ SIG Notes, 2014, 1, 1, 8, 06 Jun. 2014
    Given a graph G = (V, E) of order n and an n-dimensional non-negative vector d = (d(1), d(2),..., d(n)), called demand vector, the vector domination (resp., total vector domination) is the problem of finding a minimum S ⊆ V such that every vertex v in V ＼ S (resp., in V) has at least d(v) neighbors in S . The (total) vector domination is a generalization of many dominating set type problems, e.g., the dominating set problem, the k-tuple dominating set problem (this k is different from the solution size), and so on, and its approximability and inapproximability have been studied under this general framework. In this paper, we show that a (total) vector domination of graphs with bounded branchwidth can be solved in polynomial time. This implies that the problem is polynomially solvable also for graphs with bounded treewidth. Consequently, the (total) vector domination problem for a planar graph is subexponential fixed-parameter tractable with respect to k, where k is the size of solution., Information Processing Society of Japan (IPSJ), English
  • Posimodular Function Optimization.
    Toshimasa Ishii, Kazuhisa Makino, CoRR, abs/1410.6030, 2014
  • The (p, q)-total labeling problem for trees
    蓮沼 徹, 石井 利昌, 小野 廣隆, 宇野 裕之, 研究報告アルゴリズム（AL）, 2010, 2, 1, 8, 12 Nov. 2010
    グラフ G の k-(p,q)-全ラベリングとは，G の節点と辺への 0 から k までの整数値の割当てであり，節点とそれに接続する辺の間では少なくとも p，隣接する 2 節点間または 2 辺間では少なくとも q の差があるもののことをいう．G の (p, q)-全ラベリング数 λTp;q(G) は，k がとりうる値の最小値として定義される．G の (p, q)-全ラベリング問題とは，ラベリング数 λTp;q(G) を求める問題である．本研究では，いくつかのグラフクラスのグラフの (p, q)-全ラベリング数に対して新しい上界と下界を与える．とくに，グラフが木の場合にはタイトな上界と下界を与える．また，グラフが木で p≦3q/2 の場合に (p, q)-全ラベリング問題を解く線形時間アルゴリズムを与え，さらに最大次数が 4 以上という仮定が加わった場合，λTp;q(T) を実現する木Tを完全に特徴づけられることも示す．この結果は，(p; q)-全ラベリング問題の一般化である L (p; q)-ラベリング問題が q が p の約数でないすべての (p; q) の組に対し NP 困難であることと対照的である．A (p,q)-total labeling of a graph G is an assignment f from the vertex set V(G) and the edge set E(G) to the set of nonnegative integers such that |f(x)-f(y)| ≧ p if x is a vertex and y is an edge incident to x, and |f(x)-f(y)| ≧ q if x and y are a pair of adjacent vertices or a pair of adjacent edges, for all x and y in V(G) ∪ E(G). A k-(p,q)-total labeling is a (p,q)-total labeling f:V(G) ∪ E(G) → {0,...,k}, and the (p,q)-total labeling problem asks the minimum k, which we denote by λTp,q(G), among all possible assignments. In this paper, we first give new upper and lower bounds on λTp,q(G) for some classes of graphs G, in particular, tight bounds on λTp,q(T) for trees T. We then show that if p ≦ 3q/2, the problem for trees T is linearly solvable, and give a complete characterization of trees achieving λTp,q(T) if in addition Δ ≧ 4 holds, where Δ is the maximum degree of T. It is contrasting to the fact that the L(p,q)-labeling problem, which is a generalization of the (p,q)-total labeling problem, is NP-hard for any two positive integers p and q such that q is not a divisor of p., 情報処理学会, English
  • A linear time algorithm for L(2, 1)-labeling of trees
    HASUNUMA TORU, ISHII TOSHIMASA, ONO HIROTAKA, UNO YUSHI, 研究報告アルゴリズム（AL）, 2009, 7, 1, 8, 20 Nov. 2009
    グラフの k-L(2, 1) -ラベリングとは，頂点への 0 から k までの整数値の割り当てであり，隣接頂点間では少なくとも 2，距離 2 の頂点間では少なくとも 1 の差があるもののことを言う．L(2, 1) -ラベリング問題とは，グラフに対する k-L(2, 1) ラベリングの中で最小の k を求めるものである．この問題は，木幅が 2 のグラフに対してでも NP 困難であることが知られている．一方，多項式時間アルゴリズムは，路や閉路，木といった限られたクラスにしか知られておらず，木に対するアルゴリズムの計算量も 10 年以上 O(Δ4.5n) 時間であった （ただし，Δ はグラフの最大次数，n は木の頂点数）．この計算量は最近になって O(min{n1.75, Δ1.5n}) 時間へと改善されたが，線形時間で解けるかどうかは未解決であった．本論文では，これを解決する木の L(2, 1) -ラベリングに対する線形時間アルゴリズムを提案する．An L(2, 1)-labeling of a graph G is an assignment f from the vertex set V(G) to the set of nonnegative integers such that |f (x)− f (y)| ≥ 2 if x and y are adjacent and |f (x)− f (y)| ≥ 1 if x and y are at distance 2, for all x and y in V(G). A k-L(2, 1)-labeling is an L(2, 1)-labeling f : V(G) → {0, . . . , k}, and the L(2, 1)-labeling problem asks the minimum k, which we denote by λ(G), among all possible assignments. It is known that this problem is NP-hard even for graphs of treewidth 2, and tree is one of very few classes for which the problem is polynomially solvable. The running time of the best known algorithm for trees had been O(Δ4.5n) for more than a decade, and an O(min{n1.75, Δ1.5n})-time algorithm has appeared recently, where Δ is the maximum degree of T and n = |V(T)|, however, it has been open if it is solvable in linear time. In this paper, we finally settle this problem for L(2, 1)-labeling of trees by establishing a linear time algorithm., 情報処理学会, English
  • Posi-modular Systems with Modulotone Requirements under Permutation Constraints
    ISHII TOSHIMASA, MAKINO KAZUHISA, 研究報告アルゴリズム（AL）, 2009, 5, 1, 8, 20 Nov. 2009
    有限集合 V ，正モジュラ関数 f : 2V → R および模調関数 r : 2V → R からなるシステム (V, f, r) において，すべての X ⊆ V - R に対し f (X) ≧ r (X) が成り立つような要素数最小の集合 R ⊆ V を求める問題を考える．この問題は横断問題と呼ばれ，Sakashita ら 6) により無向グラフまたは無向ハイパーグラフにおける辺連結度要求をもつ供給点配置問題および外部ネットワーク問題を一般化した枠組みとして導入された．本論文では，任意の模調関数 r が r (X) = max｛pr (v,W) ｜ v ∈ X ⊆ V - W｝ をみたす関数 pr : V × 2V → R により特徴づけられることを示し，さらに供給点配置問題に対する Tamura らの結果 8) を一般化し，r が π-単調であるとき横断問題が簡潔な貪欲法により解けることを示す．ここで，すべての W ⊆ V と π(u) ≧ π(v) であるすべての 2 要素 u, v ∈ V に対し pr (u,W) ≧ pr (v,W) が成り立つ V の順列 π が存在するとき，r は π-単調であるという．また，r が π-単調であるときの横断問題における極小不足集合族 W に関する構造的性質も示す．すなわち，すべての点 u とその親 v に対し π(u) ≦ π(v) が成り立つような W に対する基本木が存在することを示す．この性質は，供給点配置問題に対する貪欲法の正当性の別の証明を与える．さらに，フラクショナル横断問題が，横断問題に対するアルゴリズムと同様の手法により解けることを示す．Given a system (V, f, r) on a finite set V consisting of a posi-modular function f : 2V → R and a modulotone function r : 2V → R, we consider the problem of finding a minimum set R ⊆ V such that f(X) ≧ r(X) for all X ⊆ V - R. The problem, called the transversal problem, was introduced by Sakashita et al. 6) as a natural generalization of the source location problem and external network problem with edge-connectivity requirements in undirected graphs and hypergraphs. By generalizing 8) for the source location problem, we show that the transversal problem can be solved by a simple greedy algorithm if r is π-monotone, where a modulotone function r is π-monotone if there exists a permutation π of V such that the function pr : V × 2V → R associated with r satisfies pr(u,W) ≧ pr(v,W) for all W ⊆ V and u, v ∈ V with π(u) ≧ π(v). Here we show that any modulotone function r can be characterized by pr as r(X) = max｛pr(v,W) ｜ v ∈ X ⊆ V - W｝. We also show the structural properties on the minimal deficient sets W for the transversal problem for π-monotone function r, i.e., there exists a basic tree T for W such that π(u) ≦ π(v) for all arcs (u, v) in T, which, as a corollary, gives an alternative proof for the correctness of the greedy algorithm for the source location problem. Furthermore, we show that a fractional version of the transversal problem can be solved by the algorithm similar to the one for the transversal problem., 情報処理学会, English
  • A tight upper bound on the (2,1)-total labeling number of outerplanar graphs
    Toru Hasunuma, Toshimasa Ishii, Hirotaka Ono, Yushi Uno, CoRR, abs/0911.4590, 2009
  • 2-F-11 An O(n log^2 n)-Time Algorithm for L(2,1)-Labeling of Trees
    HASUNUMA Toru, ISHII Toshimasa, ONO Hirotaka, UNO Yushi, 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 2008, 308, 309, 10 Sep. 2008
    The Operations Research Society of Japan, English
  • RA-002 An O(n log^2 n) Algorithm for L(2,1)-labeling of Trees
    Hasunuma Toru, Ishii Toshimasa, Ono Hirotaka, Uno Yushi, 情報科学技術フォーラム講演論文集, 7, 1, 5, 6, 20 Aug. 2008
    Forum on Information Technology, English
  • 木のL(2,1)-ラベリングに対するO(n^<1.75>)時間アルゴリズム
    蓮沼徹, 石井利昌, 小野廣隆, 宇野裕之, 電子情報通信学会技術研究報告. COMP, コンピュテーション, 108, 29, 43, 50, 06 May 2008
    グラフのL(2,1)-ラベリングとは,頂点集合V(G)から非負整数への割当てfで,V(G)上のすべての隣接するxとyに対し,|f(x)-f(y)|≧2を満たし,すべての距離2で離れるxとyに対し,|f(x)-f(y)|≧1を満たすもののことを言う.k-L(2,1)-ラベリングとは,f:V(G)→{0,...,k}なる割当てfであり,L(2,1)-ラベリング問題とは,そのような最小のkを求める問題のことを言い,その最小値をλ(G)で表す.この問題はグラフの木幅が2のときでもNP困難であることが知られている.木はこの問題に対して多項式時間で求解可能な数少ないグラフクラスであるが,その計算量は小さくなく,最大次数Δ,頂点数nの木Tに対し,これまでO(Δ^<4.5>n)時間アルゴリズムしか知られていなかった.本論文では,まずλ(T)=Δ+1成立の既存の必要条件がΔ=Ω(√<n>)である木においては必要条件でもあることを示す.これによりΔ=Ω(√<n>)の場合にL(2,1)-ラベリングを求める線形時間アルゴリズムが得られる.次にλ(T)が任意の木に対してO(Δ^<1.5>n)時間で計算できることを示す.これらを組み合わせることにより,これまで知られていた最善の計算時間O(Δ^<4.5>n)を大幅に改善するO(n^<1.75>)時間アルゴリズムを提案する., 社団法人電子情報通信学会
  • タンク繰りスケジューリングに対する二段階アルゴリズム(組合せ最適化)
    山田 展靖, 石井 利昌, 永持 仁, 久保田 誠, 日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, 2005, 248, 249, 16 Mar. 2005
    公益社団法人日本オペレーションズ・リサーチ学会, Japanese
  • 最小費用流アルゴリズムを用いたタンク繰りスケジューリング構成法(スケジューリング)
    高橋 健吾, 石井 利昌, 永持 仁, 武田 真人, 日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, 2004, 172, 173, 17 Mar. 2004
    公益社団法人日本オペレーションズ・リサーチ学会, Japanese
  • タンク繰りにおける経路探索法(スケジューリング)
    西垣 豊, 高橋 健吾, 石井 利昌, 永持 仁, 武田 真人, 日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, 2004, 174, 175, 17 Mar. 2004
    公益社団法人日本オペレーションズ・リサーチ学会, Japanese
  • Augmenting Node-to-Area Connectivity under Local Edge-Connectivity Requirements Based on Areas
    HAGIWARA Masayuki, ISHII Toshimasa, NAGAMOCHI Hiroshi, IEICE technical report. Theoretical foundations of Computing, 103, 31, 23, 30, 18 Apr. 2003
    Given an undirected multigraph G=(V, E), a family W of sets W ⊊ V of vertices (areas), and a requirement function r_w : W→Z^+ (where Z^+ is the set of nonnegative integers), we consider the problem of augmenting G by the smallest number of new edges so that the resulting graph has at least r_w(W) edge-disjoint paths between v and W for every pair of a vertex v ⋴ V and an area W ⋴ W. So far this problem was shown to be NP-hard in the uniform case of r_w(W)=1 for each W ⋴ W and polynomially solvable in the uniform case of r_w(W)=r≧2 for each W ⋴ W. In this paper, we show that the problem can be solved in O(m+pr^*n^5 log (n/r^*)) time, even in the general case of r_w(W)≧3 for each W &isins W, where n=|V|, m=|{ { u, v}|(u, v) &isins E}|, p=|W|, and r^*=max{r_w(W)|W &isins W}, Moreover, we give an approximation algorithm which finds a solution with at most one surplus edges over the optimal value in the same time complexity in the general case of r_w(W)≧2 for each W ⋴ W., The Institute of Electronics, Information and Communication Engineers, English
  • Constructing a Cactus for Minimum Cuts of a Graph in O(mn + n^2log n) Time and O(m) Space
    NAGAMOCHI Hiroshi, NAKAMURA Shuji, ISHII Toshimasa, The Institute of Electronics, Information and Communication Engineers Transactions on Information and Systems, D, 86, 2, 179, 185, 01 Feb. 2003
    It is known that all minimum cuts in an edge-weighted undirected graph with n vertices and m edges can be represented by a cactus with ★(n) vertices and edges, a connected graph in which each edge is contained in an exactly one cycle. In this paper, we show that such a cactus representation can be computed in ★(mn + n^2log n) time and ★(m) space. This improves the previously best complexity of deterministic cactus construction algorithms, and matches with the time bound of the fastest deterministic algorithm for computing a single minimum cut., The Institute of Electronics, Information and Communication Engineers, English
  • A simple robust algorithm for bisecting a triconnected graph with two resource sets　　　　　　　　　　　　　　　
    Hiroshi Nagamochi, Kengo Iwata, Toshimasa Ishii, Proceedings of the 7th Japan-Korea Joint Workshop on Algorithms and Computation, pp.210-222, 2003
  • Minimum Augmentation of Edge-Connectivity between Vertices and Sets of Vertices in Undirected Graphs
    ISHII Toshimasa, AKIYAMA Yoko, NAGAMOCHI Hiroshi, IEICE technical report, 102, 490, 13, 20, 22 Nov. 2002
    Given an undirected multigraph G = (V, E), a family W of areas W⫅=V and a target connectivity k ≧1, we consider the problem of augmenting G by the smallest number of new edges so that the resulting graph has at least k edge-disjoint paths between v and W for every pair of a vertex v ∈ V and an area W ∈ W. So far this problem was shown to be NP-complete in the case of k = 1 and polynomially solvable in the case of k = 2. In this paper, we show that the problem for k ≧ 3 can be solved in O(m+n(k^3+n^2)(p+kn+nlog n)logk+pkn^3log(n/k)) time, where n = |V|, m = |{ { u, v}|(u, v) ∈ E}|, and p = |W|., The Institute of Electronics, Information and Communication Engineers, English
  • A Ranged Laminar Family in Graphs and Its Application (Mathematical Optimization Theory and its Algorithm)
    Nagamochi Hiroshi, Abe Yuusuke, Ishii Toshimasa, RIMS Kokyuroku, 1241, 157, 165, Dec. 2001
    Kyoto University, English
  • An $O(mn+n^2log n)$ Time Cactus Construction Algorithm (Mathematical Optimization Theory and its Algorithm)
    Nagamochi Hiroshi, Nakamura Shuji, Ishii Toshimasa, RIMS Kokyuroku, 1241, 148, 156, Dec. 2001
    Kyoto University, English
  • On the Minimum Local-Vertex-Connectivity Augmentation in Graphs
    NAGAMOCHI Hiroshi, ISHII Toshimasa, IEICE technical report. Theoretical foundations of Computing, 101, 376, 69, 76, 12 Oct. 2001
    Given a graph G and target values r(u, v) prescribed for each pair of vartices u and v, we consider the problem of augmenting G by a smallest set F of new edges such that the resulting graph G+F has at leaset r(u, v) internally disjoint paths between each pair of vertices u and v. We show that the problem is NP-hard even if G is (k-1)-vertex-connected and r(u, v)⋴{0, k}, u, v⋴V holds for a constant k≩2. We then give a linear time algorithm which delivers a 3/2-approximation solution to the problem with a connected graph G and r(u, v)⋴{0, 2}, u, v⋴V., The Institute of Electronics, Information and Communication Engineers, English
  • Let us compute a minimum cut in a graph
    Nagamochi Hiroshi, Ishii Toshimasa, Proceedings of the IEICE General Conference, 2001, 1, 316, 317, 07 Mar. 2001
    The Institute of Electronics, Information and Communication Engineers, Japanese
  • Augmenting an (l-1)-Vertex-Connected Multigraph to a k-Edge-Connected and l-Vertex-Connected Multigraph
    ISHII Toshimasa, NAGAMOCHI Hiroshi, IBARAKI Toshihide, IEICE technical report. Theoretical foundations of Computing, 99, 30, 41, 48, 23 Apr. 1999
    Given an undirected multigraph G=(V, E) and two positive integers k and l we consider the problem of augmenting G by the smallest number of new edges to obtain a k-edge-connected and l-vertex-connected multigraph. In this paper, we show that an (l-1)-vertex-connected multigraph G (l4) can be made k-edge-connected and l-vertex-connected by adding at most 2k surplus edges over the optimum in polynomial time., The Institute of Electronics, Information and Communication Engineers, English
  • k - Edge and 3 - Vertex Connectivity Augmentation in an Arbitrary Multigraph
    ISHII Toshimasa, NAGAMOCHI Hiroshi, IBARAKI Toshihide, IPSJ SIG Notes, 1998, 98, 9, 16, 28 Oct. 1998
    Given an undirected multigraph G=(V, E) and two positive integers k and l, the edge-and-vertex connectivity augmentation problem asks to augment G by the smallest number of new edges so that the resulting multigraph becomes k-edge-connected and l-vertex-connected. In this paper, we show that the problem with a fixed k and l=3 can be solved in polynomial time for an arbitrary multigraph G., Information Processing Society of Japan (IPSJ), Japanese
  • Optimally Augmenting to Make a Biconnected Graph Four-Edge and Three-Vertex Connected
    ISHII Toshimasa, NAGAMOCHI Hiroshi, IBARAKI Toshihide, 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 1997, 262, 263, 10 Sep. 1997
    The Operations Research Society of Japan, English
  • Augmenting edge-connectivity and vertex-connectivity simultaneously
    ISHII Toshimasa, NAGAMOCHI Hiroshi, IBARAKI Toshihide, 日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, 1997, 206, 207, 02 Apr. 1997
    The Operations Research Society of Japan, English
  • A Simple and Constructive Proof of a Minimum Cut Algorithm
    NAGAMOCHI Hiroshi, ISHII Toshimasa, IBARAKI Toshihide, IPSJ SIG Notes, 1996, 100, 33, 40, 17 Oct. 1996
    For the correctness of the minimum cut algorithm proposed in [H. Nagamochi and T. Ibaraki, Computing edge-connectivity of multigraphs and capacitated graphs, SIAM J. Discrete Mathematics, 5, 1992, pp. 54-66], several, simple proofs have been presented recently. This paper gives yet another simple proof. As a byproduct, it can provide an O(mlog n) time algorithm that outputs a maximum flow between a pair of vertices s and t, which are selected by the algorithm, where n and m are numbers of the vertices and edges, respectively., Information Processing Society of Japan (IPSJ), Japanese
  • 無向グラフにおけるκ-辺分割問題の一般化について(組合せ最適化(3))
    永持 仁, 石井 利昌, 茨木 俊秀, 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 1995, 150, 151, 16 Oct. 1995
    公益社団法人日本オペレーションズ・リサーチ学会, Japanese
  • Generalized k-edge-partition problem with specified bases
    NAGAMOCHI Hiroshi, ISHII Toshimasa, IBARAKI Toshihide, IEICE technical report. Theoretical foundations of Computing, 95, 259, 45, 54, 22 Sep. 1995
    Given an undirected graph G=(V, E) with k distinct edges e_i∈E(i=1,…,k), and natural numbers m_i(i=1,…,k) such that m_1+…+m_k=|E|, the k-edge-partition problem with specified bases asks to find a partition E_1…∪E_k of E such that (1)e_i∈E_i, and |E_i|=m_i(i=1,…,k), (2)each E_i induces a connected subgraph. It has been shown that there exists such a partition E_1∪…∪E_k if G is k-edge-connected. If the input graph is k-edge-connected, polynomial time algorithms for solving this problem are known for k=2,3, but no polynomial time algorithm is known for k≥4. In this paper, we generalize the probrem as follows. Given an undirected graph G=(V,E), where each vertex has some labels chosen from a label set {1,…,k}, and natural numbers m_i(i=1,…,k) such that m_1+…+m_k=|E|, the k-edge-partition problem with specified labels asks to find a partition E_1∪…∪E_k of E such that (i)|E_i|= m_i, and (ii) each connected component induced by E_i contains a vertex which has label i. We present a sufficient condition for this problem with k=2,3 to have such a partition, and construct O(|E|) and O(|E|+|V|^2) time algorithms for finding a partition under the condition for k=2 and 3, respectively. And we show that this problem can be solved in O(|E|)(k=2), O(|E|+|V|^2)(k=3) time., The Institute of Electronics, Information and Communication Engineers, Japanese

Books and other publications

Affiliated academic society

  • 情報処理学会　　　　　　　　　　　　　　　
  • 日本オペレーションズリサーチ学会　　　　　　　　　　　　　　　
  • Control and Information Engineers　　　　　　　　　　　　　　　
  • The Operations Research Society of Japan　　　　　　　　　　　　　　　

Research Themes

  • Research on the stabilization of financial systems
    Grants-in-Aid for Scientific Research
    01 Apr. 2023 - 31 Mar. 2028
    鈴木 輝好, 石井 利昌, 宮田 亮, 西出 勝正, 施 建明, 八木 恭子
    2024年2月，東京都立大学，日本オペレーションズリサーチ学会北海道支部と共同で，国際ワークショップ，Winter Workshop on Operations Research, Finance and Mathematics, 2024 を開催した．研究協力者のKonstantin Borovkov氏（メルボルン大学），Alexander Novikov（シドニー工科大学）の他，Sebastian Jaimungal氏（トロント大学）, Juri Hinz氏（ナショナルオーストラリア銀行）, Yuri Kabanov氏（モスクワ Vega Institute Foundation）, Nino Kordzakhia氏（Macquarie University）, Yue Kuen Kwok（香港科技大学）, Vincent Liang氏（メルボルン大学）, Mikhail Zhitlukhin氏（Steklov Mathematical Institute, Moscow）を招き，国内研究者と併せて20件の発表があった．また，期間中に，国内ワークショップを同時開催し，6件の発表があった．研究協力者も含めた有意義な議論を行った．
    研究課題については，ネットワークモデルに関する既存研究における未解決の問題について，研究の拡張を行った．概要を述べると，クレジットデフォルトスワップ（CDS）と呼ばれる金融商品が銀行ネットワークの一部にある場合に，どの銀行が生き残るかが，一意に決まらない問題について，縮小写像の原理を用いた収束条件を得ることができた．経済的な解釈について納得感のある条件である点が優れている．また，本モデルでは，COCO債・劣後債を考慮することができ，優先債についてはPari-pass 条項に応じた返済を行う．これは既存モデルの中では最も現実的である．現在，投稿の準備中である．
    Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (B), Hokkaido University, 23K26326
  • ネットワーク構造を有する離散最適化問題に対する高性能アルゴリズムとその応用
    科学研究費助成事業 基盤研究(C)
    Apr. 2016 - Mar. 2022
    石井 利昌
    日本学術振興会, 基盤研究(C), 北海道大学, 16K00001
  • 再保険ネットワークのリスク管理と保険システムの救済問題に関する研究
    科学研究費助成事業 基盤研究(B)
    01 Apr. 2018 - 31 Mar. 2021
    鈴木 輝好, 石井 利昌, 宮田 亮, 西出 勝正, 施 建明, 八木 恭子
    主研究テーマについて，大きく分けて２件の研究論文を完成させた．どちらも，2020年4月現在，トップジャーナルにおいて審査中である．第一は，"Default Contagion and Systemic Risk with Cross-Ownership of Equities, Debts, and Financial Derivatives"． 研究メンバーである，一橋大学・西出，東京都立大学・八木，および代表者・北海道大学・鈴木の共著で，保険契約のネットワーク問題における最大の障害について，一つの解答を与えた．保険契約は，金融オプションでいうところのプットオプションであり，いわば売り契約ある．この場合，システミックリスクに関する従来の研究成果は，簡単には保険契約に応用できない．我々はこの点について重要な成果を得た．第二は，"The Mechanism of Endogenous Clearing and Simultaneous Defaults in Two Interconnected Firms".研究メンバーである，八木，東京理科大学・施，および研究代表者による共同研究で，2社間に債務や株式の持ち合いがある場合に，企業のデフォルトがどのようなメカニズムで発生するのかを明らかにした．問題は連立型の線形相補性問題に帰着することが示され，有用なアルゴリズムを提案し，それが収束することを示した．
    日本学術振興会, 基盤研究(B), 北海道大学, 18H01652
  • Development of efficient algorithms based on enumeration structures
    Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (B)
    01 Apr. 2014 - 31 Mar. 2020
    Makino Kazuhisa
    This research develops a fast algorithm for not only enumeration problems, but also search and optimization problems by extracting and analyzing enumeration structures and combining them with discrete optimization methods, or proving computational hardness such as NP-hardness.
    There are two major achievements: The first one is to construct a first polynomial time algorithm for the optimal composition ordering problem for
    monotone increasing linear functions. The second result is to show exponential time lower bound of positive modular function minimization and to develop a fast exponential time algorithm. These won the International Conference ISAAC Best Paper Award and FIT2015 Funai Best Paper Award, respectively.
    Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (B), Kyoto University, 26280001
  • Studies on the financial risk management and the public fund distribution under systemic risks
    Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (B)
    01 Apr. 2015 - 31 Mar. 2018
    SUZUKI Teruyoshi
    We consider a clearing system of an interbank market in the case in which cross-trading of credit default swaps among banks is present, and we investigate the effect of credit default swaps on market stability. Furthermore, a study of default decision when two firms cross-hold their issuing debts and equities are presented. We first show that the problem to evaluate the securities values issued by the two firms can be formulated by a system of partial differential equations. Then we propose a simple numerical method which is an extension of the projected successive over-relaxation method. Finally, numerical analyses are presented to investigate effects on endogenous default boundaries and default probabilities from financial and firm specific parameters
    Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (B), Hokkaido University, 15H02965
  • Studies on graph theoretical approaches for robust network design and its generalizations
    Grants-in-Aid for Scientific Research
    2012 - 2015
    Ishii Toshimasa
    In modern society, we have many networks such as traffic networks and communication networks. It is required that such networks have some fault-tolerance, because we have many natural disasters such as earthquake and flood in Japan. In this research, we proposed several efficient algorithms for the control and design of robust networks. Also, we extended these results, which may contribute to the analysis of other general problems.
    Japan Society for the Promotion of Science, Grant-in-Aid for Young Scientists (B), Hokkaido University, Principal investigator, Competitive research funding, 24700001
  • ネットワーク構造を持つ問題に対するアルゴリズム設計とその応用に関する研究　　　　　　　　　　　　　　　
    助成金
    Jan. 2012 - Dec. 2013
    石井 利昌
    栢森情報科学振興財団, Principal investigator, Competitive research funding
  • An unified evaluation model for the financial systemic risk under financial crisis
    Grants-in-Aid for Scientific Research(基盤研究(B))
    2011 - 2013
    Teruyoshi SUZUKI, Toshimasa ISHII, Masaaki KIJIMA, Katsumasa NISHIDE, 西出 勝正
    First, we presented the pricing model of the corporate securities with cross-holdings, default costs and bond seniorities. We propose an early clearing payment vector to capture the financial crisis. We showed the existence of them and the method to derive them. Second, we introduced an optimal capital injection problem and proposed an algorithm to solve it. The problem can be represented by a linear programming formulation under Eisenberg and Noe's model. We presented a sequential method to solve both the firm's payoff to debt holders and the government's capital injection to the firms. We can show that the priority rule of capital injection does not depend on the amount of the budget by the government.
    Ministry of Education, Culture, Sports, Science and Technology, 基盤研究(B), 北海道大学, Coinvestigator not use grants, Competitive research funding, 23310098
  • Studies on the design of algorithms for reliable networks and its application
    Grants-in-Aid for Scientific Research(若手研究(B))
    2008 - 2011
    Toshimasa ISHII
    Ministry of Education, Culture, Sports, Science and Technology, 若手研究(B), 小樽商科大学, Principal investigator, Competitive research funding, 20700002
  • 耐故障性を考慮したネットワーク設計問題に関するグラフアルゴリズムの研究　　　　　　　　　　　　　　　
    研究助成金
    Apr. 2008 - Mar. 2009
    石井 利昌
    稲盛財団, Principal investigator, Competitive research funding
  • 耐故障性を考慮したネットワーク設計問題に関するグラフアルゴリズムの研究
    科学研究費補助金(若手研究(B))
    2005 - 2007
    石井 利昌
    通信網・交通網,VLSIの配線,施設配置問題など現実社会において解決が求められる多くの問題が,グラフ・ネットワーク的構造を持つ組合せ最適化問題として定式化される.グラフ理論における連結度の概念は,種々のネットワークの制御・設計において,耐故障性に関する基本的な評価尺度として用いられる.本研究では,特に連結度制約を持つネットワーク設計問題を中心に,それらを解く効率的なアルゴリズムを構築することを目的とする.
    本年度は,これまで申請者が携わってきた,辺の付加により与えられた連結度要求を満たすようにグラフを増大させる連結度増大問題や,連結度要求を満たすように節点上に特別な施設(供給点)の集合を配置する供給点配置問題に対する効率的なアルゴリズムの研究をさらに推し進め,いくつかの結果を得た.例えば,点連結度要求を持つ供給点配置問題の近似可能性に関して次の結果を得た.
    ・無向グラフG=(V, E),関数c: V→R^+,関数d: V→Z^+が与えられたとき,各節点v∈VとSの間にv以外の節点を共有しないパスがd(v)本以上存在し,Σ_vc(v)が最小である節点集合Sを求める問題に対し,cが一様の場合,max{d^*, 2d^*-6}倍近似可能であることを証明した.ただし,d^*=max{d(v) | v∈V}である.この問題は、これまで,P=NPでない限り,ある定数cに対してcln(Σ_vd(v))倍より良い近似ができないことが知られている.また,cが一様かつ,d^*が定数のときでさえ,問題はNP困難であることが知られている.本研究の成果により,d^*が定数の場合は,cが一様であれば定数倍近似可能であることを示した.また,d^*が定数の場合でもAPX困難であることも示した.
    文部科学省, 若手研究(B), 豊橋技術科学大学->小樽商科大学, Principal investigator, Competitive research funding, 17700011
  • Webコンテンツ活用に関連した離散最適化問題の研究
    科学研究費補助金(特定領域研究)
    2004 - 2007
    増山 繁, 中山 慎一, 本間 宏利, 相田 慎, 梅村 恭司, 石井 利昌
    Webコンテンツ活用に関連して、1.要約,検索など,Webコンテンツを知的活動において活用するのを支援するための技術に対する基本アルゴリズムの確立,2.Webコンテンツ配信方法を求める問題のグラフ理論的定式化とその解法,に重点をおいて研究を実施してきた.
    1に関する19年度のおもな成果は以下のとおりである.企業業績や景気動向要因表現の新聞記事からの統計的手法による少数の手がかり表現を与えるだけで要因表現を抽出できる抽出法を考案した.
    更に、企業業績要因にpositiveかnegativeかの極性を付与するアルゴリズムも考案した。また、基礎として、Webページから本文部分のみを切り出す手法も考案した。
    2に関するおもな成果は以下のとおりである.
    外平面グラフ上での最小枝ランキング問題に対する多項式時間アルゴリズムを考案した.また、ネットワーク信頼性に関連して多重グラフにおける連結全域部分木の数え上げに関係した不等式の証明ヤ、サーキュラアークグラフ上での要節点を求める並列アルゴリズム等の成果を得た。配信のためのサーバを配置する問題に関連して、3つのソースを持つ4連結グラフを2分割する問題、局所的3節点連結性を満足するソース配置問題、無向グラフ上での節点連結性の要求を満たすソース配置問題に対するグリーディ近似アルゴリズム等の研究を行った。
    文部科学省, 特定領域研究, 豊橋技術科学大学, Coinvestigator not use grants, Competitive research funding, 16092213
  • Construction of Approximation Algorithms Based on Graph Theory and Its Application to Network Problems
    Grants-in-Aid for Scientific Research(基盤研究(C))
    2002 - 2004
    Hiroshi NAGAMOCHI, Yoshiyuki KARUNO, Toshimasa ISHII
    By using sparsification technique by maximum adjacency order, we obtained an O(n^2(1+min{κ^2, κ√}/δ)) time and O(-n+m) space algorithm that computes a 2-approximation solution for the problem of finding a minimum vertex cut in a graph G, where n,m,κ and δ denote the number of vertices, the number of edges, the vertex-connectivity and the minimum degree in G, respectively.
    For the problem of finding a minimum (s,t)-cut in a digraph with a source s and a sink t, we introduced a new parameter μ that measures undirectedness of a given digraph, and gave an O(min{m+ν(ν+μ)^<1/2>n,(ν+μ)^<1/6>nm^<2/3> } }) time algorithm, where ν denotes the size of a minimum (s,t)-cut.
    For the problem of augmenting a given connected graph to meet biconnectivity between a prescribed pair, we designed a linear time 4/3-approximation algorithm.
    We also surveyed a recent progress on graph algorithms for network connectivity problems. We showed that the extreme set problem, the cactus representation problem, the edge-connectivity augmentation problem and the source location problem can be solved in O(mn+n^2log n) time by using maximum adjacency order.
    Ministry of Education, Culture, Sports, Science and Technology, 基盤研究(C), 豊橋技術科学大学->京都大学, Coinvestigator not use grants, Competitive research funding, 14580372
  • グラフの連結度増大問題に関する研究
    科学研究費補助金(奨励研究(A), 若手研究(B))
    2001 - 2002
    石井 利昌
    グラフの古典的な連結度である辺連結度または点連結度を増大させる問題を中心に,グラフの連結度に関する問題の研究,高速アルゴリズムの開発・実装を行った.
    まず,任意のh-点連結グラフを,l-辺連結かつk-点連結に同時に増大させる問題に対し,最適値との絶対誤差が0(l(k-h))以内である近似解を多項式時間で求めるアルゴリズムをはじめて構築した.これまで,点連結度のみを増大させる問題でも,最適値との絶対誤差が0(k(k-h))以内の近似解を求めるアルゴリズムが知られている程度だが,本結果は,本質的に異なる概念である辺連結度と点連結度を同時に考慮しても,同等の近似比を得ることに成功したことを示す結果である.
    また,最近注目されてきている,2点の間ではなく,点と点集合(領域)の間の連結度を表わす概念であるNA連結度に関する問題に対して,次の結果を得た.グラフと領域集合が与えられたとき,全ての点と領域間のNA辺連結度を目標値k以上にする問題に対し,k≧3のとき,多項式時間で解けることをはじめて示した.これまで,この問題に関して,k=1のときNP-困難,k=2のときは多項式時間で解けることが知られていたが,k≧3の場合は,多項式時間で解けるかどうか未解決であった.
    また,連結度増大問題とは別に,NA連結度に関する問題の1つである供給点配置問題に関して,次の結果を得た.ここで,供給点配置問題とは,各点が要求されたNA連結度を満たすように,領域を配置する問題である.各点が3以下に限定された局所点連結度要求を持つ問題に対し,線形時間アルゴリズムの存在を示した.さらに,4以上の局所点連結度要求を持つ場合は,NP-困難であることも示した.
    文部科学省, 奨励研究(A), 若手研究(B), 豊橋技術科学大学, Principal investigator, Competitive research funding, 13780224
  • Development of algorithms for solving graph/network problems
    Grants-in-Aid for Scientific Research(特定領域研究(B))
    1998 - 2000
    Hiroshi NAGAMOCHI, Toshimasa ISHII
    In this research, we have developed efficient graph algorithms and clarified graph structures in the graph/network problems.
    We have obtained the following results for the problems related to connectivity. We have improved the time complexity for representing all minimum cuts in a cactus. To achieve this, we used a maximum adjacency ordering, a graph search procedure by which all minimum cuts can be found without using the maximum-flow algorithm. A subset of edges is called a k-cut if removal of it results in k components. We have reduced the time bound for computing a minimum k-cut for k=3,4,5,6 by a new approach that enumerates 2-cut in the nondecreasing order of weights. We have proved that necessary information to solve the k-edge-connectivity augmentation problem can be extracted from an appropriate set of cuts with size less than k in a given graph. By using such a set of cuts, we can control structure of solutions to the edge-connectivity augmentation problem.
    We have also obtained the following results in designing approximation algorithms. For the vertex-connectivity problem with a target value k, an approximation algorithm was proposed only for the case where a given graph is (k-1)-vertex-connected. We extend the algorithm so that it works for an arbitrary input graph. Our algorithm delivers an solution with absolute error 2(α-k)k, where α =the vertex-connectivity of an input graph. We have studied the problem of increasing the edge- and vertex-connectivities at the same time, and gave an approximation algorithm with absolute error that depends only on the target values. We have also designed a (7/2)-approximation algorithm for the weighted 3-vertex-connectivity augmentation problem, a 2-approximation algorithm for the weighted minimum edge dominating set problem and a dH(r)-approximation algorithm for the network design problem in hypergraph with degree d, where r is the maximum demand and H() is the harmonic function.
    Ministry of Education, Culture, Sports, Science and Technology, 特定領域研究(B), 京都大学->豊橋技術科学大学, Coinvestigator not use grants, Competitive research funding, 10205213

syllabus

  • 卒業論文, 2024年, 学士課程, 経済学部
  • オペレーションズ・リサーチ特論Ａ, 2024年, 修士課程, 経済学院
  • 論文, 2024年, 修士課程, 経済学院
  • オペレーションズ・リサーチ特論Ｂ, 2024年, 修士課程, 経済学院
  • 現代経済経営演習, 2024年, 博士後期課程, 経済学院
  • 現代経済経営演習Ⅰ, 2024年, 修士課程, 経済学院
  • 現代経済経営演習Ⅱ, 2024年, 修士課程, 経済学院
  • オペレーションズ・リサーチⅠ, 2024年, 学士課程, 経済学部
  • 演習Ⅰ（２単位）, 2024年, 学士課程, 経済学部
  • 演習Ⅱ（２単位）, 2024年, 学士課程, 経済学部
  • 演習Ⅲ（２単位）, 2024年, 学士課程, 経済学部
  • 演習Ⅳ（２単位）, 2024年, 学士課程, 経済学部
  • 演習Ⅴ（２単位）, 2024年, 学士課程, 経済学部
  • 演習Ⅵ（２単位）, 2024年, 学士課程, 経済学部
  • 演習Ⅶ（２単位）, 2024年, 学士課程, 経済学部
  • 演習Ⅷ（２単位）, 2024年, 学士課程, 経済学部
  • 現代日本制度ⅠD, 2024年, 学士課程, 現代日本学プログラム課程
  • 経営科学Ⅱ, 2024年, 学士課程, 経済学部