石井　利昌 (イシイ　トシマサ)

経済学研究院　現代経済経営部門　経営分析分野教授
Last Updated :2025/11/11

■研究者基本情報

学位

  • 博士(情報学), 京都大学

Researchmap個人ページ

ホームページURL

J-Global ID

研究キーワード

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

研究分野

  • 情報通信, 情報学基礎論

担当教育組織

■経歴

経歴

  • 2016年09月 - 現在
    北海道大学 大学院経済学研究院, 教授
  • 2012年04月 - 2016年08月
    北海道大学, 大学院経済学研究科, 准教授
  • 2006年04月 - 2012年03月
    小樽商科大学, 商学部社会情報学科, 助教授 (2006年) 准教授 (2007年～)
  • 2000年04月 - 2006年03月
    豊橋技術科学大学, 工学部情報工学科, 助手

学歴

  • 1999年04月 - 2000年03月, 京都大学, 大学院情報学研究科, 数理工学専攻, 日本国
  • 2000年, 京都大学, Graduate School, Division of Information and Communication
  • 1995年04月 - 1999年03月, 京都大学, 大学院工学研究科, 数理工学専攻
  • 1991年04月 - 1995年03月, 京都大学, 工学部, 数理工学科, 日本国
  • 1995年, 京都大学, Faculty of Engineering

■研究活動情報

受賞

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

論文

その他活動・業績

  • 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 : 信学技報, 114, 80, 1, 8, 2014年06月13日
    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., 一般社団法人電子情報通信学会, 英語
  • (Total) Vector Domination for Graphs with Bounded Branchwidth
    Toshimasa Ishii, Hirotaka Ono, Yushi Uno, 研究報告アルゴリズム（AL）, 2014, 1, 1, 8, 2014年06月06日
    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.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., 一般社団法人情報処理学会, 英語
  • Posimodular Function Optimization.
    Toshimasa Ishii, Kazuhisa Makino, CoRR, abs/1410.6030, 2014年
  • 木の(p, q)-全ラベリング問題
    蓮沼 徹, 石井 利昌, 小野 廣隆, 宇野 裕之, 研究報告アルゴリズム（AL）, 2010, 2, 1, 8, 2010年11月12日
    グラフ 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., 情報処理学会, 英語
  • 木のL(2, 1)-ラベリングに対する線形時間アルゴリズム
    蓮沼 徹, 石井 利昌, 小野 廣隆, 宇野 裕之, 研究報告アルゴリズム（AL）, 2009, 7, 1, 8, 2009年11月20日
    グラフの 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., 情報処理学会, 英語
  • 順列制約をみたす模調要求をもつ正モジュラシステムについて
    石井 利昌, 牧野 和久, 研究報告アルゴリズム（AL）, 2009, 5, 1, 8, 2009年11月20日
    有限集合 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., 情報処理学会, 英語
  • 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
    蓮沼徹, 石井利昌, 小野廣隆, 宇野裕之, 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 2008, 308, 309, 2008年09月10日
    社団法人日本オペレーションズ・リサーチ学会, 英語
  • RA-002 木のL(2,1)-ラベリングのためのO(n log^2 n)時間アルゴリズム(モデル・アルゴリズム・プログラミング,査読付き論文)
    蓮沼 徹, 石井 利昌, 小野 廣隆, 宇野 裕之, 情報科学技術フォーラム講演論文集, 7, 1, 5, 6, 2008年08月20日
    FIT(電子情報通信学会・情報処理学会)運営委員会, 英語
  • 木のL(2,1)-ラベリングに対するO(n^<1.75>)時間アルゴリズム
    蓮沼徹, 石井利昌, 小野廣隆, 宇野裕之, 電子情報通信学会技術研究報告. COMP, コンピュテーション, 108, 29, 43, 50, 2008年05月06日
    グラフの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, 2005年03月16日
    公益社団法人日本オペレーションズ・リサーチ学会, 日本語
  • 最小費用流アルゴリズムを用いたタンク繰りスケジューリング構成法(スケジューリング)
    高橋 健吾, 石井 利昌, 永持 仁, 武田 真人, 日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, 2004, 172, 173, 2004年03月17日
    公益社団法人日本オペレーションズ・リサーチ学会, 日本語
  • タンク繰りにおける経路探索法(スケジューリング)
    西垣 豊, 高橋 健吾, 石井 利昌, 永持 仁, 武田 真人, 日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, 2004, 174, 175, 2004年03月17日
    公益社団法人日本オペレーションズ・リサーチ学会, 日本語
  • 領域毎に連結度要求の異なるNA辺連結度増大問題について
    萩原 正之, 石井 利昌, 永持 仁, 電子情報通信学会技術研究報告. COMP, コンピュテーション, 103, 31, 23, 30, 2003年04月18日
    無向グラフG=(V, E),節点部分集合(領域)族W={W_1,…, W_p}_1 W_1⊊V,要求関数r_w : W→Z^+(Z^+は非負整数集合を表す)が与えられたとき,Gに最小本数の辺を加えることで,節点v⋴Vと節点部分集合W⋴Wの全ての組において,vとW間に辺素な路がr_w(W)本以上存在するグラフを構築する問題を考える。これまで,この問題は,各領域W⋴Wについての連結度要求r_w (W)が一定値rの場合,r=1ならば,NP-困難であり,r≧2ならば,多項式時間で解けることが知られていた。本研究では,連結度要求が領域毎に異なる場合でも,各領域W⋴Wにおいてr_w(W)≧3ならば,この問題がO(m+pr^*n^5 log (n/r^*))時間で解けることを示す。このとき,n=|V|, m=|{ { u, v}|(u, v)⋴E}|, p=|W|, r^*=max{r_w(W)|W⋴W}である。さらに,各領域W⋴Wにおいてr_w(W) ≧2のとき,同時間で最適値との絶対誤差が1以内の解が見つかることを示す。, 一般社団法人電子情報通信学会, 英語
  • 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, IEICE transactions on information and systems, 86, 2, 179, 185, 2003年02月01日
    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., 一般社団法人電子情報通信学会, 英語
  • 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年
  • 無向グラフにおける節点領域間の辺連結度を増大させる問題について
    石井 利昌, 秋山 容子, 永持 仁, 電子情報通信学会技術研究報告. COMP, コンピュテーション, 102, 490, 13, 20, 2002年11月22日
    無向グラフG = (V,E),節点部分集合族W={W_1,...,W_p},W_i⫅=V,整数k≧1が与えられたとき,Gに最小本数の辺を加えることで,節点v∈Vと節点部分集合W∈Wの全ての組において,vとW間に辺素な路がk本以上存在するグラフを構築する問題を考える.この問題は,これまでk=1の場合NP-完全で,k=2の場合多項式時間で解けることが知られている.本研究では,k≧3の場合,この問題がO(m+n(k^3+n^2)(p+kn+nlogn)logk+pkn^3log(n/k))時間で解けることを示す。このとき,n=|V|,m=|{ { u,v}|(u,v)∈E}|,p=|W|である., 一般社団法人電子情報通信学会, 英語
  • A Ranged Laminar Family in Graphs and Its Application (数理最適化の理論とアルゴリズム)
    永持 仁, 阿部 勇介, 石井 利昌, 数理解析研究所講究録, 1241, 157, 165, 2001年12月
    京都大学, 英語
  • An O(mn+n2logn) Time Cactus Construction Algorithm (数理最適化の理論とアルゴリズム)
    永持 仁, 中村 秀司, 石井 利昌, 数理解析研究所講究録, 1241, 148, 156, 2001年12月
    京都大学, 英語
  • 無向グラフにおける局所点連結度増大問題について
    永持 仁, 石井 利昌, 電子情報通信学会技術研究報告. COMP, コンピュテーション, 101, 376, 69, 76, 2001年10月12日
    無向グラフG=(V, E)と全ての2点対u, v⋴Vに対して目標値r(u, v)が与えられたとき, 最少本数の辺集合FをGに加えることで, 全ての2点u, v⋴V間に互いに点素な路がr(u, v)本以上存在するグラフを構成する問題を考える.本研究では, Gが(k-1)-点連結でk≩2である定数kに対してr(u, v)⋴{o, k}, u, v⋴Vが成立する場合においても, この問題がNP-困難であることを示す.また, Gが連結で全ての2点対u, v⋴Vに対しr(u, v)⋴{0, 2}である場合に, 最適値の3/2倍以下の解を線形時間で出力するアルゴリズムを与える., 一般社団法人電子情報通信学会, 英語
  • TD-1-10 グラフの最小カットを計算しよう
    永持 仁, 石井 利昌, 電子情報通信学会総合大会講演論文集, 2001, 1, 316, 317, 2001年03月07日
    一般社団法人電子情報通信学会, 日本語
  • (l-1)-点連結ブラフをk-辺連結かつl-点連結に増大させる問題
    石井 利昌, 永持 仁, 茨木 俊秀, 電子情報通信学会技術研究報告. COMP, コンピュテーション, 99, 30, 41, 48, 1999年04月23日
    辺連結度, 点連結度を同時に最適増大させる問題とは, 入力として, 無向多重グラフG=(V, E)と, 2つの正整数k,l が与えられたとき, 最小本数の辺をGに加えることで, グラフの辺連結度および点連結度をそれぞれk以上, かつl以上にする問題である. 本研究では, 入力グラフが(l-1)-点連結グラフ(l4)である場合, この問題に対して, 最適解との差が2k以下である近似解を出力する多項式時間アルゴリズムを構築する., 一般社団法人電子情報通信学会, 英語
  • グラフをk?辺連結かつ3-点連結に最適増大させる問題
    石井 利昌, 永持仁, 茨木 俊秀, 情報処理学会研究報告アルゴリズム（AL）, 1998, 98, 9, 16, 1998年10月28日
    辺連結度，点連結度を同時に最適増大させる問題とは，入力として，無向多重グラフG＝（V，E）と，2つの正整数k，lが与えられたとき，最小本数の辺をGに加えることで，グラフの辺連結度および点連結度をそれぞれk以上，かつl以上にする問題である．本研究では，kが任意に固定された正整数でl＝3である場合，この問題が，任意の入力グラフに対して，多項式時間で解けることを示す．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., 一般社団法人情報処理学会, 日本語
  • Optimally Augmenting to Make a Biconnected Graph Four-Edge and Three-Vertex Connected
    石井 利昌, 永持 仁, 茨木 俊秀, 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 1997, 262, 263, 1997年09月10日
    公益社団法人日本オペレーションズ・リサーチ学会, 英語
  • Augmenting edge-connectivity and vertex-connectivity simultaneously
    石井 利昌, 永持 仁, 茨木 俊秀, 日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, 1997, 206, 207, 1997年04月02日
    公益社団法人日本オペレーションズ・リサーチ学会, 英語
  • 最小カット問題の簡潔かつ構成的な証明
    永持仁, 石井 利昌, 茨木 俊秀, 情報処理学会研究報告アルゴリズム（AL）, 1996, 100, 33, 40, 1996年10月17日
    [H．Nagamochi and T．Ibaraki，Computing edge?connectivity of multigraphs and capacitated graphs，SIAM J．Discrete Mathematics，5，1992，pp．54?66]により提案された，最小カットを求めるアルゴリズムの正当性について，近年，いくつかの簡潔な証明が紹介されている．本研究では，これらとはまた別の簡潔な証明を示す．またこの証明は構成的であり，ある特別な2点対s，t間の最大フローをO( log )時間で求めるアルゴリズムを構築する(，mはそれぞれグラフの点数，辺数である）．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(m log 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., 一般社団法人情報処理学会, 日本語
  • 無向グラフにおけるκ-辺分割問題の一般化について(組合せ最適化(3))
    永持 仁, 石井 利昌, 茨木 俊秀, 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 1995, 150, 151, 1995年10月16日
    公益社団法人日本オペレーションズ・リサーチ学会, 日本語
  • 無向グラフにおけるk-辺分割問題の一般化について
    永持 仁, 石井 利昌, 茨木 俊秀, 電子情報通信学会技術研究報告. COMP, コンピュテーション, 95, 259, 45, 54, 1995年09月22日
    G=(V,E)を無向グラフとする.指定辺付k-辺分割問題は,Gのk本の辺e_1,…,e_kおよび辺数|E|のk個の正整数への分割m_1+…+m_k=|E|が与えられたとき,次の(1)(2)を満たすEの分割E_1∪…∪E_kを求める問題である.(1)e_1∈E_i,|E_i|=m_i(i=1,…,k,(2)各E_iに誘導される部分グラフが連結になる.Gがk-辺連結ならば,(1)(2)を満たす分割が必ず存在することが知られているが,分割を具体的に多項式時間で求めるアルゴリズムはk≤3の場合にのみ知られており,k>4については未解決である.本報告では,より一般化したラベル指定k-辺分割問題を導入する.すなわち,Gの各点に{1,…,k}から選んだラベルを自由に付したグラフ,および辺数の分割m_1+…+m_k=|E|に対し,次の(i)-(ii)の条件を満たす辺集合Eの分割E_1,…,E_kを求める問題である.(i)|E_i|=m_i(i=1,…,k),(ii)各E_iの誘導するグラフの各連結成分はラベルiのついた点を少なくとも1個含む.本報告では,k=2,3の場合について,この問題の分割が存在する十分条件を与え,この条件の下で分割を見つけるO(|E|)時間(k=2の場合)および,O(|E|+|V|^2)時間(k=3の場合)の多項式時間アルゴリズムを構築する., 一般社団法人電子情報通信学会, 日本語

書籍等出版物

所属学協会

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

共同研究・競争的資金等の研究課題

  • 金融システムの安定化に関する研究
    科学研究費助成事業
    2023年04月01日 - 2028年03月31日
    鈴木 輝好, 石井 利昌, 宮田 亮, 西出 勝正, 施 建明, 八木 恭子
    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 条項に応じた返済を行う．これは既存モデルの中では最も現実的である．現在，投稿の準備中である．
    日本学術振興会, 基盤研究(B), 北海道大学, 23K26326
  • ネットワーク構造を有する離散最適化問題に対する高性能アルゴリズムとその応用
    科学研究費助成事業 基盤研究(C)
    2016年04月 - 2022年03月
    石井 利昌
    日本学術振興会, 基盤研究(C), 北海道大学, 16K00001
  • 再保険ネットワークのリスク管理と保険システムの救済問題に関する研究
    科学研究費助成事業 基盤研究(B)
    2018年04月01日 - 2021年03月31日
    鈴木 輝好, 石井 利昌, 宮田 亮, 西出 勝正, 施 建明, 八木 恭子
    主研究テーマについて，大きく分けて２件の研究論文を完成させた．どちらも，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
  • 列挙構造を利用した高速アルゴリズム開発
    科学研究費助成事業 基盤研究(B)
    2014年04月01日 - 2020年03月31日
    牧野 和久, 高澤 兼二郎, 石井 利昌, 藤重 悟
    本研究は，列挙構造を抽出・解析し，離散最適化の手法と融合させることにより，列挙問題ばかりでなく，探索問題や最適化問題などに対する高速なアルゴリズムの開発、あるいは、NP困難性など計算量的な下界を与えることに成功した。
    具体的な成果として大きなもの以下の２つがある。1つ目の成果は、単調増加線形関数の最適合成順問題に関する初めての多項式時間アルゴリズムを構成したことである。2番目の成果は正モジュラ関数最小化の指数時間下界と高速指数時間アルゴリズムの開発による成果である。これらはそれぞれ国際会議ISAACのBest Paper AwardとFIT2015船井ベストペーパー賞を受賞した。
    日本学術振興会, 基盤研究(B), 京都大学, 26280001
  • システミックリスクの下での金融リスク管理と公的資金配分に関する研究
    科学研究費助成事業 基盤研究(B)
    2015年04月01日 - 2018年03月31日
    鈴木 輝好, 石井 利昌, 西出 勝正, 施 建明, 八木 恭子, 宮田 亮
    システミックリスクの基礎研究を進め，クレジットデフォルトスワップを銀行が保有する場合について，既存研究の拡張を行った．その結果，単純な負債のネットワークでは，コンプリートリンクは金融を安定させると言われていたCDSのネットワークでは，逆にシステミックリスクを顕在化させることを示した．また，より単純な2企業間でのネットワーク問題については，連立型線形相補性問題に帰着することを示し，求解が不動点問題に帰着することを導いた．さらには，その不動点問題は，ある条件のもとで解が存在することを示し．また，そのアルゴリズムを提案した．
    日本学術振興会, 基盤研究(B), 北海道大学, 15H02965
  • ロバストなネットワーク設計のためのグラフ論的アプローチとその一般化に関する研究
    科学研究費補助金(若手研究(B))
    2012年 - 2015年
    石井 利昌
    現代社会では，交通網や通信網などネットワーク構造を持つものが数多くみられる．地震や洪水など自然災害が多発する中，これらにはある程度の故障が起きても対処できるロバストな構造が求められる．本研究では，ロバストなネットワーク制御・設計が求められる問題を対象に，効率的なアルゴリズムをいくつか提案した．また，これらの結果をネットワーク以外の一般的な問題にも応用するための拡張についていくつかの結果を得た．
    文部科学省, 若手研究(B), 小樽商科大学->北海道大学, 研究代表者, 競争的資金, 24700001
  • ネットワーク構造を持つ問題に対するアルゴリズム設計とその応用に関する研究　　　　　　　　　　　　　　　
    助成金
    2012年01月 - 2013年12月
    石井 利昌
    栢森情報科学振興財団, 研究代表者, 競争的資金
  • 金融システム破綻の経済損失とそのリスクに関する統一的定量化モデルの開発
    科学研究費補助金(基盤研究(B))
    2011年 - 2013年
    鈴木 輝好, 石井 利昌, 木島 正明, 西出 勝正, 西出 勝正
    システミックリスクの下での企業負債の評価モデルを開発し，また金融システム破綻時の，政府による資本注入問題を最適化問題として定式化し，これを解く手法を提案した．両研究ともに，本研究費助成金を用いて開催した国際シンポジウム（北海道大学）および諸外国における国際学会において発表した．どちらの研究も，発展可能性の高い基礎的枠組を提供している．前者については，システミックリスクを考慮する上で，より発展的な動的モデルへの拡張可能性を持つ．後者については，経済破綻時における不可逆的な経済損失を考慮にいれることが課題である．
    文部科学省, 基盤研究(B), 北海道大学, 連携研究者, 競争的資金, 23310098
  • ネットワークの信頼性向上のためのアルゴリズム設計とその応用に関する研究
    科学研究費補助金(若手研究(B))
    2008年 - 2011年
    石井 利昌
    文部科学省, 若手研究(B), 小樽商科大学, 研究代表者, 競争的資金, 20700002
  • 耐故障性を考慮したネットワーク設計問題に関するグラフアルゴリズムの研究　　　　　　　　　　　　　　　
    研究助成金
    2008年04月 - 2009年03月
    石井 利昌
    稲盛財団, 研究代表者, 競争的資金
  • 耐故障性を考慮したネットワーク設計問題に関するグラフアルゴリズムの研究
    科学研究費補助金(若手研究(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), 豊橋技術科学大学->小樽商科大学, 研究代表者, 競争的資金, 17700011
  • Webコンテンツ活用に関連した離散最適化問題の研究
    科学研究費補助金(特定領域研究)
    2004年 - 2007年
    増山 繁, 中山 慎一, 本間 宏利, 相田 慎, 梅村 恭司, 石井 利昌
    Webコンテンツ活用に関連して、1.要約,検索など,Webコンテンツを知的活動において活用するのを支援するための技術に対する基本アルゴリズムの確立,2.Webコンテンツ配信方法を求める問題のグラフ理論的定式化とその解法,に重点をおいて研究を実施してきた.
    1に関する19年度のおもな成果は以下のとおりである.企業業績や景気動向要因表現の新聞記事からの統計的手法による少数の手がかり表現を与えるだけで要因表現を抽出できる抽出法を考案した.
    更に、企業業績要因にpositiveかnegativeかの極性を付与するアルゴリズムも考案した。また、基礎として、Webページから本文部分のみを切り出す手法も考案した。
    2に関するおもな成果は以下のとおりである.
    外平面グラフ上での最小枝ランキング問題に対する多項式時間アルゴリズムを考案した.また、ネットワーク信頼性に関連して多重グラフにおける連結全域部分木の数え上げに関係した不等式の証明ヤ、サーキュラアークグラフ上での要節点を求める並列アルゴリズム等の成果を得た。配信のためのサーバを配置する問題に関連して、3つのソースを持つ4連結グラフを2分割する問題、局所的3節点連結性を満足するソース配置問題、無向グラフ上での節点連結性の要求を満たすソース配置問題に対するグリーディ近似アルゴリズム等の研究を行った。
    文部科学省, 特定領域研究, 豊橋技術科学大学, 連携研究者, 競争的資金, 16092213
  • グラフ理論に基づく近似アルゴリズムの構築とネットワーク問題への応用
    科学研究費補助金(基盤研究(C))
    2002年 - 2004年
    永持 仁, 軽野 義行, 石井 利昌
    ・最大隣接順序によるグラフ疎化法を利用して,O(n^2(1+min{κ^2,κ√n}/δ))時間,O(n+m)領域の計算量で,点連結度κに対する2倍近似の点カットを計算するアルゴリズムを得た(δはグラフの最小次数).提案するアルゴリズムはδがκと比べて大きい場合には従来よりも高い性能を発揮する.
    ・グラフにソース,シンクと呼ぶ2点s,tが与えられたとき,ソースシンク間の最小(s,t)-カットを求める問題に対しては,有向グラフに対し,無向グラフへの「近さ」を表す指標μを導入し,有向グラフDの最小(s,t)-カットをO(min{m+ν(ν+μ)^<1/2>n,(ν+μ)^<1/6>nm^<2/3> } })時間で計算するアルゴリズムを設計した(νは最小(s,t)-カットの値).この計算量は小さなμを持ちかつ密であるような有向グラフに対しては従来法よりも優れた性能を発揮する.
    ・与えられた単純連結グラフG=(V,E)および2点対の集合Rに対して,何本かの新しい枝をグラフGに付与してRの各2点対間の局所点連結度を2以上にする問題を考える.このとき加える枝の本数を最小にすることが目的である.問題に対する下界の導き方を精密化することで最適な付加枝集合の大きさの高々4/3倍の解を求める線形時間アルゴリズムを設計した.
    ・ネットワーク連結度問題に対する最近の進展についてサーベイを行った.多くのネットワークの連結度問題は最大流最小カットの定理に基づく考察から最大流アルゴリズムを利用したアルゴリズムにより解くことができるが,最近,最大隣接順序と呼ばれる節点の順序付けを利用することで無向ネットワークにおいてはさらに効率の高いアルゴリズムが設計できることが示されている.特に,n,mをネットワークの節点数,枝数としたとき,極値節点集合問題,カクタス表現問題,枝連結度増大問題,供給点配置問題と呼ばれる問題に対してはO(mn+n^2log n)時間のアルゴリズムが設計できることを示す.この計算時間はネットワークの最小カットの値を決定する現在最良の計算量に等しい.これらの多くのアルゴリズムに対して研究代表者により現在最良の計算時間が達成されている.
    文部科学省, 基盤研究(C), 豊橋技術科学大学->京都大学, 連携研究者, 競争的資金, 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), 豊橋技術科学大学, 研究代表者, 競争的資金, 13780224
  • グラフ・ネットワーク問題を解くアルゴリズムの研究
    科学研究費補助金(特定領域研究(B))
    1998年 - 2000年
    永持 仁, 石井 利昌
    本研究ではグラフ構造の解明,高速グラフアルゴリズムの開発を行った.
    グラフの連結性に関する問題について以下の結果を得た.重み付き無向グラフのすべての最小カットを,カクタスと呼ばれるグラフ構造に表現するアルゴリズムの計算量を軽減した.ここで使われている手法は最大隣接順序というグラフの探索法であり,すべての最小カットを計算するために最大流アルゴリズムを必要としない点が特徴である.グラフをk-分割する枝集合はk-カットと呼ばれる.最小k-カットを求める問題に対し,グラフの2-カットを大きさの小さい順に部分的に列挙するという新しいアプローチにより,k=3,4,5,6に対して従来の計算量を改善した.k-辺連結でないグラフにおいて,カット値がk未満のカットから適当なものをいくつか互いに交叉しないように選んでやると,グラフの連結度増大問題を解くために必要な情報が取り出せるという性質を示した.あらかじめこのようなカットの集合を求めておけば,連結度増大問題における解の形を細かく制御できることを示した.
    近似解を求めるアルゴリズムについて以下の結果を得た.グラフの点連結度増大問題は,これまで,目標の点連結度kに対し,入力のグラフの点連結度が(k-1)である場合にしか解法が知られていなかったが,新たに,入力グラフの連結度が任意である場合のアルゴリズムを与えた.このアルゴリズムは最適解に比べ,高々2(k-α)k本しか余分に付加辺を使わない解を計算する(ここでα=(入力グラフの点連結度)).さらに連結度増大問題では点連結度と辺連結度を同時に扱うものも研究し,目標値のみに依存する絶対誤差の近似アルゴリズムを得た.この他,相対誤差のアルゴリズムとして,重み付き3点連結化問題に対する(7/2)-近似アルゴリズム,最小重み辺支配集合問題に対する2-近似アルゴリズム,次数dのハイパーグラフ上のネットワーク設計問題に対するdH(r)-近似アルゴリズムを設計した(rは連結度の最大要求量,H<>は調和関数).
    文部科学省, 特定領域研究(B), 京都大学->豊橋技術科学大学, 連携研究者, 競争的資金, 10205213