研究者データベース

石井 利昌(イシイ トシマサ)
経済学研究院 現代経済経営部門 経営分析分野
教授

基本情報

所属

  • 経済学研究院 現代経済経営部門 経営分析分野

職名

  • 教授

学位

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

ホームページ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年   京都大学
  • 1995年04月 - 1999年03月   京都大学   大学院工学研究科   数理工学専攻
  • 1991年04月 - 1995年03月   京都大学   工学部   数理工学科
  •         - 1995年   京都大学

所属学協会

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

研究活動情報

論文

  • Magnús M. Halldórsson, Toshimasa Ishii, Kazuhisa Makino, Kenjiro Takazawa
    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 10389 437 - 448 2017年 [査読有り][通常論文]
     
    A function f : 2V → IR on a finite set V is posimodular if f(X) + f(Y) ≥ f(X\\Y) + f(Y\\X), for all X, Y ⊆ V. Posimodular functions often arise in combinatorial optimization such as undirected cut functions. We consider the problem of finding a nonempty subset X minimizing f(X), when the posimodular function f is given by oracle access. We show that posimodular function minimization requires exponential time, contrasting with the polynomial solvability of submodular function minimization that forms another generalization of cut functions. On the other hand, the problem is fixed-parameter tractable in terms of the size of the image (or range) of f. In more detail, we show that Ω(20.3219nTf) time is necessary and O(20.92nTf) sufficient, where Tf denotes the time for one function evaluation. When the image of f is D = {0, 1,...,d}, O(21.271dnTf) time is sufficient and Ω(20.1609dTf) necessary. We can also generate all sets minimizing f in time 2O(d) n2Tf . Finally, we also consider the problem of maximizing a given posimodular function, showing that it requires at least 2n−1Tf time in general, while it has time complexity Θ(nd−1Tf) when D = {0, 1,...,d} is the image of f, for integer d.
  • Toshimasa Ishii, Hirotaka Ono, Yushi Uno
    Discrete Optimization 22 111 - 121 2016年11月01日 [査読有り][通常論文]
     
    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 (total) dominating set problem, the (total) k-dominating set problem (this k is different from the solution size), and so on, and subexponential fixed-parameter algorithms with respect to solution size for apex-minor-free graphs (so for planar graphs) are known. In this paper, we consider maximization versions of the problems that is, for a given integer k, the goal is to find an S⊆V with size k that maximizes the total sum of satisfied demands. For these problems, we design subexponential fixed-parameter algorithms with respect to k for apex-minor-free graphs.
  • Toshimasa Ishii, Hirotaka Ono, Yushi Uno
    DISCRETE APPLIED MATHEMATICS 207 80 - 89 2016年07月 [査読有り][通常論文]
     
    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 subset of V such that every vertex nu in V \ S (resp., in V) has at least d(nu) 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. (C) 2016 Elsevier B.V. All rights reserved.
  • Toshimasa Ishii, Kazuhisa Makino
    ALGORITHMICA 69 1 130 - 147 2014年05月 [査読有り][通常論文]
     
    Given a directed or undirected graph G=(V,E), a collection of two disjoint subsets of V, and a requirement function , we consider the problem (called area-to-area edge-connectivity augmentation problem) of augmenting G by a smallest number of new edges so that the resulting graph satisfies for all XaS dagger V, with SaS dagger XaS dagger V-T, where d (G) (X) denotes the degree of a vertex set X in G. This problem can be regarded as a natural generalization of the global, local, and node-to-area edge-connectivity augmentation problems. In this paper, we show that there exists a constant c such that the problem is inapproximable within a ratio of , unless P=NP, even restricted to the directed global node-to-area edge-connectivity augmentation or undirected local node-to-area edge-connectivity augmentation. We also provide an -approximation algorithm for the area-to-area edge-connectivity augmentation problem, which is a natural extension of Kortsarz and Nutov's algorithm (Kortsarz and Nutov, J. Comput. Syst. Sci., 74:662-670, 2008). This together with the negative result implies that the problem is -approximable, unless P=NP, which solves open problems for node-to-area edge-connectivity augmentation in Ishii et al. (Algorithmica, 56:413-436, 2010), Ishii and Hagiwara (Discrete Appl. Math., 154:2307-2329, 2006), Miwa and Ito (J. Oper. Res. Soc. Jpn., 47:224-243, 2004). Furthermore, we characterize the node-to-area and area-to-area edge-connectivity augmentation problems as the augmentation problems with modulotone and k-modulotone functions.
  • Toshimasa Ishii, Hirotaka Ono, Yushi Uno
    LATIN 2014: THEORETICAL INFORMATICS 8392 238 - 249 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 subset of 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.
  • Toshimasa Ishii, Hirotaka Ono, Yushi Uno
    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 8596 292 - 304 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 subexponential fixed-parameter algorithms with respect to solution size for apex-minor-free graphs (so for planar graphs) are known. In this paper, we consider maximization versions of the problems that is, for a given integer k, the goal is to find an S ⊆ V with size k that maximizes the total sum of satisfied demands. For these problems, we design subexponential fixed-parameter algorithms with respect to k for apex-minor-free graphs. © 2014 Springer International Publishing.
  • Toru Hasunuma, Toshimasa Ishii, Hirotaka Ono, Yushi Uno
    IJNC 4 2 251 - 259 2014年 [査読有り][通常論文]
  • Toshimasa Ishii
    JOURNAL OF GRAPH THEORY 74 4 392 - 416 2013年12月 [査読有り][通常論文]
     
    Given an undirected graph G=(V,E) and an integer D1, we consider the problem of augmenting G by a minimum set of new edges so that the diameter becomes at most D. It is known that no constant factor approximation algorithms to this problem with an arbitrary graph G can be obtained unless P=NP, while the problem with only a few graph classes such as forests is approximable within a constant factor. In this article, we give the first constant factor approximation algorithm to the problem with an outerplanar graph G. We also show that if the target diameter D is even, then the case where G is a partial 2-tree is also approximable within a constant. (C) 2013 Wiley Periodicals, Inc. J. Graph Theory 74: 392-416, 2013
  • Toru Hasunuma, Toshimasa Ishii, Hirotaka Ono, Yushi Uno
    Algorithmica 66 3 654 - 681 2013年07月 [査読有り][通常論文]
     
    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.5 n) for more than a decade, and an O(min{n 1.75,Δ 1.5 n})-time algorithm has appeared recently, where Δ and n are the maximum degree and the number of vertices of an input tree, however, it has been open if it is solvable in linear time. In this paper, we finally settle this problem by establishing a linear time algorithm for L(2,1)-labeling of trees. Furthermore, we show that it can be extended to a linear time algorithm for L(p,1)-labeling with a constant p. © 2012 Springer Science+Business Media, LLC.
  • Toru Hasunuma, Toshimasa Ishii, Hirotaka Ono, Yushi Uno
    Journal of Discrete Algorithms 14 189 - 206 2012年07月 [査読有り][通常論文]
     
    A (2,1)-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 {0,1,...,k} of nonnegative integers such that |f(x)-f(y)|≥2 if x is a vertex and y is an edge incident to x, and |f(x)-f(y)|≥1 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). The (2,1)-total labeling number λ T 2 (G) of G is defined as the minimum k among all possible (2,1)-total labelings of G. In 2007, Chen and Wang conjectured that all outerplanar graphs G satisfy λ T 2 (G)≤Δ(G)+2, where Δ(G) is the maximum degree of G. They also showed that it is true for G with Δ(G)≥5. In this paper, we solve their conjecture, by proving that λ T 2 (G)≤Δ(G)+2, even when Δ(G)≤4. © 2011 Elsevier B.V.
  • Toru Hasunuma, Toshimasa Ishii, Hirotaka Ono, Yushi Uno
    DISCRETE MATHEMATICS 312 8 1407 - 1420 2012年04月 [査読有り][通常論文]
     
    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 left perpendicularf(x) - f (y)right perpendicular >= p if x is a vertex and y is an edge incident to x, and left perpendicularf(x) - f (y)right perpendicular >= 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) U E(G). A k-(p, q)-total labeling is a (p, q)-total labeling f : V (G) boolean OR E(G) -> {0, ..., k}, and the (p, q)-total labeling problem asks the minimum k, which we denote by Apl.q (G), among all possible assignments. In this paper, we first give new upper and lower bounds on lambda(T)(p,q)(G) for some classes of graphs G, in particular, tight bounds on lambda(T)(p,q)(T) for trees T. We then show that if p <= 3q/2, the problem for trees T is linearly solvable, and completely determine lambda(T)(p,q)(T) for trees T with Delta >= 4, where Delta 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. (C) 2012 Elsevier B.V. All rights reserved.
  • Toshimasa Ishii
    2012 THIRD INTERNATIONAL CONFERENCE ON NETWORKING AND COMPUTING (ICNC 2012) 393 - 398 2012年 [査読有り][通常論文]
     
    In communication networks, the distance between two nodes is one measure of transfer delay between them. Thus, it is required that the diameter of the network, which is defined as the maximum distance between every two nodes in it, is relatively small. This paper surveys computational results on graph augmentation problems which model network design problems with diameter requirements, initiated in [F. R. K. Chung and M. R. Garey, "Diameter bounds for altered graphs," J. Graph Theory, vol. 8, pp. 511-534, 1984].
  • Toshimasa Ishii
    Eighteenth Computing: The Australasian Theory Symposium, CATS 2012, Melbourne, Australia, January 2012 123 - 132 Australian Computer Society 2012年 [査読有り][通常論文]
  • Toshimasa Ishii, Yoko Akiyama, Hiroshi Nagamochi
    ALGORITHMICA 56 4 413 - 436 2010年04月 [査読有り][通常論文]
     
    Given an undirected multigraph G = (V, E), a familyW of areas W subset of 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 is an element of V and an area W is an element of 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 + n log n)log k + pkn(3) log (n/k)) time, where n = vertical bar V vertical bar, m = vertical bar{ { u, v}vertical bar(u, v) is an element of E}vertical bar, and p = vertical bar W vertical bar.
  • Toru Hasunuma, Toshimasa Ishii, Hirotaka Ono, Yushi Uno
    Combinatorial Algorithms - 21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010, Revised Selected Papers 103 - 106 Springer 2010年 [査読有り][通常論文]
  • Toru Hasunuma, Toshimasa Ishii, Hirotaka Ono, Yushi Uno
    Algorithms and Computation - 21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part II 49 - 60 Springer 2010年 [査読有り][通常論文]
  • Toshimasa Ishii, Kazuhisa Makino
    Discrete Math., Alg. and Appl. 2 1 61 - 76 2010年 [査読有り][通常論文]
  • Toshimasa Ishii
    Journal of Discrete Algorithms 7 4 570 - 578 2009年12月 [査読有り][通常論文]
     
    Let G = (V, E) be a simple undirected graph with a set V of vertices and a set E of edges. Each vertex v ∈ V has a demand d (v) ∈ Z+, and a cost c (v) ∈ R+, where Z+ and R+ denote the set of nonnegative integers and the set of nonnegative reals, respectively. The source location problem with vertex-connectivity requirements in a given graph G asks to find a set S of vertices minimizing ∑v ∈ S c (v) such that there are at least d (v) pairwise vertex-disjoint paths from S to v for each vertex v ∈ V - S. It is known that the problem is not approximable within a ratio of O (ln ∑v ∈ V d (v)), unless NP has an O (Nlog log N)-time deterministic algorithm. Also, it is known that even if every vertex has a uniform cost and d* = 4 holds, then the problem is NP-hard, where d* = max {d (v) | v ∈ V}. In this paper, we consider the problem in the case where every vertex has uniform cost. We propose a simple greedy algorithm for providing a max {d*, 2 d* - 6}-approximate solution to the problem in O (min {d*, sqrt(| V |)} d* | V |2) time, while we also show that there exists an instance for which it provides no better than a (d* - 1)-approximate solution. Especially, in the case of d* ≤ 4, we give a tight analysis to show that it achieves an approximation ratio of 3. We also show the APX-hardness of the problem even restricted to d* ≤ 4. © 2009 Elsevier B.V. All rights reserved.
  • Toru Hasunuma, Toshimasa Ishii, Hirotaka Ono, Yushi Uno
    THEORETICAL COMPUTER SCIENCE 410 38-40 3702 - 3710 2009年09月 [査読有り][通常論文]
     
    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 lambda(G), among all possible L(2, 1)-labelings. It is known that this problem is NP-hard even for graphs of treewidth 2. Tree is one of a few classes for which the problem is polynomially solvable, but still only an O(Delta(4.5)n) time algorithm for a tree T has been known so far, where Delta is the maximum degree of T and n = vertical bar V(T)vertical bar. In this paper, we first show that an existent necessary condition for lambda(T) = Delta + 1 is also sufficient for a tree T with Delta = Omega(root n), which leads to a linear time algorithm for computing lambda(T) under this condition. We then show that lambda(T) can be computed in O(Delta(1.5)n) time for any tree T. Combining these, we finally obtain an O(n(1.75)) time algorithm, which substantially improves upon previously known results. (C) 2009 Elsevier B.V. All rights reserved.
  • Toshimasa Ishii
    DISCRETE OPTIMIZATION 6 1 23 - 36 2009年02月 [査読有り][通常論文]
     
    For a Finite ground set V, we call a set-function r : 2(V) --> Z(+) monotone, if r(X') >= r(X) holds for each X' subset of X subset of V, where Z(+) is the set of nonnegative integers. Given an undirected multigraph G = (V, E) and a monotone requirement function r : 2(V) --> Z(+). we consider the problem of augmenting G by a smallest number of new edges, so that the resulting graph G' satisfies d(G')(X) >= r(X) for each empty set not equal X subset of V, where d(G)(X) denotes the degree of a vertex set X in G. This problem includes the edge-connectivity augmentation problem, and in general, it is NP-hard, even if a polynomial time oracle for r is available. In this paper, we show that the problem can be solved in O(n(4)(m + n log n + q)) time, under the assumption that each empty set not equal X subset of V satisfies r(X) 2 whenever r(X) > 0, where n = vertical bar V vertical bar, m = vertical bar{ { u, v} vertical bar (u, v) is an element of E}vertical bar, and q is the time required to compute r(X) for each X subset of V. (C) 2008 Elsevier B.V. All rights reserved.
  • Toshimasa Ishii, Kazuhisa Makino
    Algorithms and Computation, 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings 473 - 482 Springer 2009年 [査読有り][通常論文]
  • Toru Hasunuma, Toshimasa Ishii, Hirotaka Ono, Yushi Uno
    Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009. Proceedings 35 - 46 Springer 2009年 [査読有り][通常論文]
  • Toshimasa Ishii, Kazuhisa Makino
    Theory of Computing 2009, Fifteenth Computing: The Australasian Theory Symposium, CATS 2009, Wellington, New Zealand, January 2009 43 - 49 Australian Computer Society 2009年 [査読有り][通常論文]
  • Toru Hasunuma, Toshimasa Ishii, Hirotaka Ono, Yushi Uno
    Algorithm Theory - SWAT 2008, 11th Scandinavian Workshop on Algorithm Theory, Gothenburg, Sweden, July 2-4, 2008, Proceedings 185 - 197 Springer 2008年 [査読有り][通常論文]
  • Toshimasa Ishii, Hitoshi Fujita, Hiroshi Nagamochi
    DISCRETE APPLIED MATHEMATICS 155 18 2523 - 2538 2007年11月 [査読有り][通常論文]
     
    Let G = (V, E) be a simple undirected graph with a set V of vertices and a set E of edges. Each vertex v epsilon V has an integer valued demand d(v) >= 0. The source location problem with vertex-connectivity requirements in a given graph G asks to find a set S of vertices with the minimum cardinality such that there are at least d(v) vertex-disjoint paths between S and each vertex v epsilon V - S. In this paper, we show that the problem with d(v) <= 3, v epsilon V can be solved in linear time. Moreover, we show that in the case where d (v) >= 4 for some vertex upsilon epsilon V, the problem is NP-hard. (c) 2007 Elsevier B.V. All rights reserved.
  • Toshimasa Ishii, Kengo Iwata, Hiroshi Nagamochi
    DISCRETE APPLIED MATHEMATICS 155 11 1441 - 1450 2007年06月 [査読有り][通常論文]
     
    Let G = (V, E) be an undirected graph with a node set V and an arc set E. G has k pairwise disjoint subsets T-1, T-2,..., T-k of nodes, called resource sets, where vertical bar T-i vertical bar is even for each i. The partition problem with k resource sets asks to find a partition V-1 and V-2 of the node set V such that the graphs induced by V-1 and V-2 are both connected and vertical bar V-1 n T-i vertical bar = vertical bar V-2 boolean AND T-i vertical bar = vertical bar T-i vertical bar/2 holds for each i = 1. 2,..., k. The problem of testing whether such a bisection exists is known to be NP-hard even in the case of k = 1. On the other hand, it is known that if G is (k + 1)-connected for k = 1, 2, then a bisection exists for any given resource sets, and it has been conjectured that for k >= 3, a (k + 1)-connected graph admits a bisection. In this paper, we show that for k = 3, the conjecture does not hold, while if G is 4-connected and has K-4 as its subgraph, then a bisection exists and it can be found in O(vertical bar V vertical bar(3) log vertical bar V vertical bar) time. Moreover, we show that for an arc-version of the problem, the (k + 1)-edge-connectivity suffices for k = 1, 2, 3. (c) 2007 Elsevier B.V. All rights reserved.
  • Toshimasa Ishii, Hitoshi Fujita, Hiroshi Nagamochi
    THEORETICAL COMPUTER SCIENCE 372 1 81 - 93 2007年03月 [査読有り][通常論文]
     
    Let G = (V, E) be a simple undirected graph with a set V of vertices and a set E of edges. Each vertex v E V has a demand d(V) epsilon Z(+) and a cost c(v) epsilon R+, where Z(+) and R+ denote the set of nonnegative integers and the set of nonnegative reals, respectively. The source location problem with vertex-connectivity requirements in a given graph G requires finding a set S of vertices minimizing Sigma(v epsilon S) c(v) such that there are at least d(v) pairwise vertex-disjoint paths from S to v for each vertex v epsilon V - S. It is known that if there exists a vertex v epsilon V with d(v) >= 4, then the problem is NP-hard even in the case where every vertex has a uniform cost. In this paper, we show that the problem can be solved in O(vertical bar V vertical bar(4) log(2) vertical bar V vertical bar) time if d(v) <= 3 holds for each vertex v epsilon V. (c) 2006 Elsevier B.V. All rights reserved.
  • Toshimasa Ishii
    Algorithms and Computation, 18th International Symposium, ISAAC 2007, Sendai, Japan, December 17-19, 2007, Proceedings 29 - 40 Springer 2007年 [査読有り][通常論文]
  • Toshimasa Ishii
    Theory of Computing 2007. Proceedings of the Thirteenth Computing: The Australasian Theory Symposium (CATS2007). January 30 - Febuary 2, 2007, Ballarat, Victoria, Australia, Proceedings 91 - 100 Australian Computer Society 2007年 [査読有り][通常論文]
  • Toshimasa Ishii, Masayuki Hagiwara
    DISCRETE APPLIED MATHEMATICS 154 16 2307 - 2329 2006年11月 [査読有り][通常論文]
     
    Given an undirected multigraph G = (V, E), a family W of sets W subset of V of vertices (areas), and a requirement function r : 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) edge-disjoint paths between v and W for every pair of a vertex v is an element of V and an area W is an element of W. So far this problem was shown to be NP-hard in the uniform case of r(W) = 1 for each W is an element of W, and polynomially solvable in the uniform case of r(W) = r >= 2 for each W is an element of W. In this paper, we show that the problem can be solved in O(m + pn(4) (r* + log n)) time, even if r(W) >= 2 holds for each W is an element of W, where n = vertical bar V vertical bar, m = vertical bar{ { u, v})vertical bar(u, v) is an element of E}vertical bar, p = vertical bar W vertical bar, and r* = max{r(W)vertical bar W is an element of W}. (c) 2006 Elsevier B.V. All rights reserved.
  • Toshimasa Ishii, Shigeyuki Yamamoto, Hiroshi Nagamochi
    DISCRETE OPTIMIZATION 3 2 154 - 164 2006年06月 [査読有り][通常論文]
     
    Given a graph G = (V, E) and an integer D >= 1, we consider the problem of augmenting G by the smallest number of new edges so that the diameter becomes at most D. It is known that no constant approximation algorithms to this problem with an arbitrary graph G can be obtained unless P = NP. For a forest G and an odd D >= 3, it was open whether the problem is approximable within a constant factor. In this paper, we give the first constant factor approximation algorithm to the problem with a forest G and an odd D; our algorithm delivers an 8-approximate solution in O(vertical bar V vertical bar(3)) time. We also show that a 4-approximate solution to the problem with a forest G and an odd D can be obtained in linear time if the augmented graph is additionally required to be biconnected. (c) 2006 Elsevier B.V. All rights reserved.
  • T Ishii, H Nagamochi, T Ibaraki
    ALGORITHMICA 44 3 257 - 280 2006年04月 [査読有り][通常論文]
     
    For two integers k, l > 0 and an undirected multigraph G = (V, E), we consider the problem of augmenting G by the smallest number of new edges to obtain an l-edge-connected and k-vertex-connected multigraph. In this paper we show that a (k - 1)-vertex-connected multigraph G can be made l-edge-connected and k-vertex-connected by adding at most max{l + 1, 2k - 4} surplus edges over the optimum in O( min{k,root n}kn(3) + n(4)) time, where n = vertical bar V vertical bar.
  • H Nagamochi, K Iwata, T Ishii
    THEORETICAL COMPUTER SCIENCE 341 1-3 364 - 378 2005年09月 [査読有り][通常論文]
     
    Given two disjoint subsets T-1 and T-2 of nodes in a 3-connected graph G = (V, E) with a node set V and an arc set E, where vertical bar T(1)vertical bar and vertical bar T(2)vertical bar are even numbers, it is known that V can be partitioned into two sets V-1 and V-2 such that the graphs induced by V-1 and V-2 are both connected and vertical bar v(1) boolean AND T(j)vertical bar = vertical bar V-2 boolean AND T(j)vertical bar = T(j)vertical bar/2 holds for each j = 1,2. Ano(vertical bar V vertical bar(2) log vertical bar V vertical bar) time and O(vertical bar V vertical bar + vertical bar E vertical bar) space algorithm for finding such a bipartition has been proposed based on a geometric argument, where G is embedded in the plane R-2 and the node set is bipartitioned by a ham-sandwich cut on the embedding. A naive implementation of the algorithm, however, requires high precision real arithmetic to distinguish two close points in a large set of points on R-2. In this paper, we propose an O(vertical bar V vertical bar(2)) time and space algorithm to the problem. The new algorithm, which remains to be based on the geometric embedding, can construct a solution purely combinatorially in the sense that it does not require computing actual embedded points in R-2 and thereby no longer needs to store any real number for embedded points. Although the new algorithm seems to need more space complexity, it can be implemented only with vertical bar V vertical bar linked lists such that each element stores an integer in [1, vertical bar V vertical bar]. (c) 2005 Elsevier B.V. All rights reserved.
  • 石井 利昌, 永持 仁, 西垣 豊, 高橋 健吾, 武田 真人
    システム/制御/情報 : システム制御情報学会誌 = Systems, control and information 49 6 213 - 221 システム制御情報学会 2005年06月 [査読有り][通常論文]
  • T Ishii, K Iwata, H Nagamochi
    ALGORITHMS AND COMPUTATION 3827 176 - 185 2005年 [査読有り][通常論文]
     
    Let G=(V, E) be an undirected graph with a node set V and an arc set E. G has k pairwise disjoint subsets T-1, T-2,..., T-k Of nodes, called resource sets, where vertical bar T(i)vertical bar is even for each i. The partition problem with k resource sets asks to find a partition V-1 and V-2 of the node set V such that the graphs induced by V-1 and V-2 are both connected and vertical bar V-1 boolean AND T(i)vertical bar = vertical bar V-2 boolean AND T(i)vertical bar = vertical bar T(i)vertical bar/2 holds for each i=1, 2,...,k. The problem of testing whether such a bisection exists is known to be NP-hard even in the case of k=1. On the other hand, it is known that that if G is (k+1)-connected for k=1, 2, then a bisection exists for any given resource sets, and it has been conjectured that for k >= 3, a (k+1)-connected graph admits a bisection. In this paper, we show that for k = 3, the conjecture does not hold, while if G is 4-connected and has K-4 as its subgraph, then a bisection exists and it can be found in O(vertical bar V vertical bar(3) log vertical bar V vertical bar) time. Moreover, we show that for an arc-version of the problem, the (k+1) -edge-connectivity suffices for k=1, 2, 3.
  • Toshimasa Ishii, Hitoshi Fujita, Hiroshi Nagamochi
    Theory of Computing 2005, Eleventh CATS 2005, Computing: The Australasian Theory Symposium, Newcastle, NSW, Australia, January/February 2005 97 - 105 Australian Computer Society 2005年 [査読有り][通常論文]
  • H Nagamochi, T Suzuki, T Ishii
    INFORMATION PROCESSING LETTERS 89 5 223 - 226 2004年03月 [査読有り][通常論文]
     
    In this paper, we consider the problem of determining whether a given graph is a maximal planar graph or not. We show that a simple linear time algorithm can be designed based on canonical orderings. Our algorithm needs no sophisticated data structure and is significantly easy to implement compared with the existing planarity testing algorithms. (C) 2003 Elsevier B.V. All rights reserved.
  • H Nagamochi, T Ishii
    DISCRETE APPLIED MATHEMATICS 129 2-3 475 - 486 2003年08月 [査読有り][通常論文]
     
    Given a graph G and target values r(u,v) prescribed for each pair of vertices 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 least r(u,v) internally disjoint paths between each pair of vertices u and v. We show that the problem is NP-hard even if for some constant k greater than or equal to 2 G is (k-1)-vertex-connected and r(u,v) is an element of {0,k} holds for u,v is an element of V. 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) is an element of {0,2}, u,v is an element of V. (C) 2003 Elsevier B.V. All rights reserved.
  • NAGAMOCHI Hiroshi, NAKAMURA Shuji, ISHI Toshimasa
    IEICE transactions on information and systems 86 2 179 - 185 一般社団法人電子情報通信学会 2003年02月 [査読有り][通常論文]
  • T. Ishii, H. Fujita and H. Nagamochi: Source location problem with local 3-vertex-connectivity requirements
    Proceedings of the 3rd Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications pp.368-377 2003年 [査読有り][通常論文]
  • T Ishii, M Hagiwara
    MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2003, PROCEEDINGS 2747 490 - 499 2003年 [査読有り][通常論文]
     
    Given an undirected multigraph G = (V, E), a family W of sets W subset of or equal to V of vertices (areas), and a requirement function r(W) : W --> Z(+) (where Z+ is the set of positive 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 upsilon and W for every pair of a vertex upsilon is an element of V and an area W is an element of W. So far this problem was shown to be NP-hard in the uniform case of r(W) (W) = 1 for each W G W, and polynomially solvable in the uniform case of r(W)(W) = r greater than or equal to 2 for each W E 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) greater than or equal to 3 for each W is an element of W, where n = \V\, m = \{ { u,v]\(u,v) is an element of E}\, p= \W\, and r* = max{r(W)(W) \W is an element of 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) greater than or equal to 2 for each W is an element of W.
  • T Ishii, S Yamamoto, H Nagamochi
    ALGORITHMS AND COMPUTATION, PROCEEDINGS 2906 434 - 443 2003年 [査読有り][通常論文]
     
    Given a graph G = (V, E), and an integer D greater than or equal to 1, we consider the problem of augmenting G by the smallest number of new edges so that the diameter becomes at most D. It is known that no constant approximation algorithms to this problem with an arbitrary graph G can be obtained unless P = NP.. For a forest G and an odd D greater than or equal to 3, it was open whether the problem is approximable within a constant factor. In this paper, we give the first constant factor approximation algorithm to the problem with a forest. G and an odd D; our algorithm delivers an 8-approximate; solution in O(\V\(3)) time. We also show that a 4-approximate solution to the problem with a forest G and an odd D can be obtained in linear time if an augmented graph is additionally required to be biconnected.
  • Toshimasa Ishii, Yoko Akiyama, Hiroshi Nagamochi
    Electr. Notes Theor. Comput. Sci. 78 236 - 259 2003年 [査読有り][通常論文]
  • H Nagamochi, T Ishii, H Ito
    INFORMATION PROCESSING LETTERS 80 6 287 - 293 2001年12月 [査読有り][通常論文]
     
    Given a digraph (or an undirected graph) G = (V, E) with a set V of vertices v with nonnegative real costs w(v), and a set E of edges and a positive integer k, we deal with the problem of finding a minimum cost subset S subset of or equal to V such that, for each vertex v epsilon V - S, there are k vertex-disjoint paths from S to v. In this paper, we show that the problem can be solved by a greedy algorithm in O(min{k.rootn}nm) time in a digraph (or in O(min(k,rootn)kn(2)) time in an undirected graph), where n = vertical bar V vertical bar and m = vertical bar E vertical bar. Based on this, given a digraph and two integers k and l, we also give a polynomial time algorithm for finding a minimum cost subset S subset of or equal to V such that for each vertex V E V - S, there are k vertex-disjoint paths from S to v as well as e vertex-disjoint paths from v to S. (C) 2001 Elsevier Science B.V. All rights reserved.
  • T Ishii, H Nagamochi, T Ibaraki
    NETWORKS 37 3 144 - 155 2001年05月 [査読有り][通常論文]
     
    Given an undirected multigraph G =(V, E) and a requirement function r(lambda): ((V)(2)) --> Z(+) (where ((V)(2)) is the set of all pairs of vertices and Z+ is the set of nonnegative integers), we consider the problem of augmenting G by the smallest number of new edges so that the local edge-connectivity and vertex-connectivity between every pair x, y is an element of V become at least r(lambda) (x, y) and two, respectively. In this paper, we show that the problem can be solved in O(n(3)(m + n) log(n(2)/(m + n))) time, where n and m are the numbers of vertices and pairs of adjacent vertices in G, respectively. This time complexity can be improved to O((nm + n? log n) log n), in the case of the uniform requirement r lambda (x, y) = l for all x, y is an element of V. Furthermore, for the general r(lambda), we show that the augmentation problem that preserves the simplicity of the resulting graph can be solved in polynomial time for any fixed l* = max{r lambda (x, y) \ x, y is an element of V}. (C) 2001 John Wiley & Sons, Inc.
  • H Nagamochi, T Ishii
    ALGORITHMS AND COMPUTATION, PROCEEDINGS 2223 124 - 135 2001年 [査読有り][通常論文]
     
    Given a graph G and target values r(u, v) prescribed for each pair of vertices 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 least 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) is an element of {0, k}, u, v is an element of V holds for a constant k greater than or equal to 2. We then give a linear time algorithm which delivers a (3)/(2)-Lapproximation solution to the problem with a connected graph G and r(u, V) E {0, 2}, u,v is an element of V.
  • T Ishii, H Nagamochi
    ALGORITHM THEORY - SWAT 2000 1851 286 - 299 2000年 [査読有り][通常論文]
     
    Given an undirected graph G = (V, E) and a positive integer k, we consider the problem of augmenting G by the smallest number of new edges to obtain a k-vertex-connected graph. In this paper, we show that, for k greater than or equal to 4 and k greater than or equal to l+2, an l-vertex-connected graph G can be made k-vertex-connected by adding at most delta (k-1)+max{0, (delta -1)(l-3)-1} surplus edges over the optimum in O(delta (k(2)n(2) + k(3)n(3/2))) time, where delta = k - l and n = /V/.
  • Toshimasa Ishii, Hiroshi Nagamochi
    Algorithms and Computation, 11th International Conference, ISAAC 2000, Taipei, Taiwan, December 18-20, 2000, Proceedings 326 - 337 Springer 2000年 [査読有り][通常論文]
  • Toshimasa Ishii, Hiroshi Nagamochi, Toshihide Ibaraki
    J. Comb. Optim. 4 1 35 - 77 2000年 [査読有り][通常論文]
  • H Nagamochi, T Ishii, T Ibaraki
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES E82A 10 2231 - 2236 1999年10月 [査読有り][通常論文]
     
    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 so far. 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 the pair of vertices s and t selected by the algorithm, where n and m are the numbers of vertices and edges, respectively. This algorithm can be used to speed up the algorithm to compute DAG(s,t) that represents all minimum cuts separating vertices s and t in a graph G, and the algorithm to compute the cactus Gamma(G) that represents all minimum cuts in G.
  • Toshimasa Ishii, Hiroshi Nagamochi, Toshihide Ibaraki
    Algorithms - ESA '99, 7th Annual European Symposium, Prague, Czech Republic, July 16-18, 1999, Proceedings 414 - 425 Springer 1999年 [査読有り][通常論文]
  • Toshimasa Ishii, Hiroshi Nagamochi, Toshihide Ibaraki
    Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 25-27 January 1998, San Francisco, California. 280 - 289 ACM/SIAM 1998年 [査読有り][通常論文]
  • T Ishii, H Nagamochi, T Ibaraki
    ALGORITHMS AND COMPUTATIONS 1533 159 - 168 1998年 [査読有り][通常論文]
     
    Given an undirected multigraph G = (V, E) and two positive integers l and k, the edge-and-vertex connectivity augmentation problem asks to augment G by the smallest number of new edges so that the resulting multigraph becomes e-edge-connected and Ic-vertex-connected. In this paper, we show that the problem with a fixed l and k = 3 can be solved in polynomial time for an arbitrary multigraph G.
  • Toshimasa, I, N Hiroshi, Toshihide, I
    ALGORITHMS AND COMPUTATION, PROCEEDINGS 1350 102 - 111 1997年 [査読有り][通常論文]
     
    Given an undirected multigraph G = (V, E) and requirement functions r(lambda) : ((V)(2)) --> Z(+) and r(kappa) : ((V)(2)) --> 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 edge-connectivity and vertex-connectivity between every pair x,y is an element of V become at least r(lambda)(x,y) and r(kappa)(x,y), respectively, in the resulting graph G '. In this paper, we show that the problem can be solved in polynomial time if r(kappa) is given by r(kappa)(x,y) = 2 for all x,y is an element of V.

書籍

その他活動・業績

  • Toshimasa Ishii, Kazuhisa Makino CoRR abs/1410.6030 2014年 [査読無し][通常論文]
  • Toshimasa Ishii, Hirotaka Ono, Yushi Uno CoRR abs/1306.5041 2013年 [査読無し][通常論文]
  • Toru Hasunuma, Toshimasa Ishii, Hirotaka Ono, Yushi Uno CoRR abs/0911.4590 2009年 [査読無し][通常論文]
  • Toru Hasunuma, Toshimasa Ishii, Hirotaka Ono, Yushi Uno CoRR abs/0810.0906 2008年 [査読無し][通常論文]
  • T. Ishii, H. Fujita and H. Nagamochi: Minimum cost source location problem with local 3-vertex-connectivity requirements
    Computing Theory: The Australian Theory Symposium (CATS'05) pp. 97-105 2005年 [査読無し][通常論文]
  • H. Nagamochi, T. Suzuki and T. Ishii: A simple recognition of maximal planar graphs
    Information Processing Letters vol.89, no.5, pp. 223-226 2004年 [査読無し][通常論文]
  • H. Nagamochi and T. Ishii: On the minimum local-vertex-connectivity augmentation in graphs
    Discrete Applied Mathematics vol.129, pp. 475-486 2003年 [査読無し][通常論文]
  • T. Ishii, Y. Akiyama and H. Nagamochi: Minimum augmentation of edge-connectivity between vertices and sets of vertices in undirected graphs
    Electronic Notes in Theoretical Computer Science, vol.78, Computing Theory: The Australian Theory Symposium (CATS'03) 2003年 [査読無し][通常論文]
  • H. Nagamochi, K. Iwata, T. Ishii: A simple robust algorithm for bisecting a triconnected graph with two resource sets
    Proceedings of the 7th Japan-Korea Joint Workshop on Algorithms and Computation pp.210-222 2003年 [査読無し][通常論文]
  • T. Ishii and M. Hagiwara: Augmenting local edge-connectivity between vertices and vertex subsets in undirected graphs
    Lecture Notes in Computer Science, vol.2747, Springer-Verlag, 28th International Symposium on Mathematical Foundations of Computer Science pp.490-499 2003年 [査読無し][通常論文]
  • T. Ishii, S. Yamamoto, and H. Nagamochi: Augmenting forests to meet odd diameter requirements
    Lecture Notes in Computer Science, vol.2906, Springer-Verlag, 14th Annual International Symposium on Algorithms and Computation (ISAAC 03) pp. 434-443 2003年 [査読無し][通常論文]
  • T. Ishii, H. Nagamochi and T. Ibaraki: Multigraph augmentation under biconnectivity and general edge-connectivity requirements
    Networks , Vol.37, pp.144-155. 2001年 [査読無し][通常論文]
  • H. Nagamochi, T. Ishii and H. Ito: Minimum cost source location problem with vertex-connectivity requirements in digraphs
    Information Processing Letters vol.80, no.6, pp. 287-294 2001年 [査読無し][通常論文]
  • T. Ishii and H. Nagamochi: On the minimum augmentation of an $\ell$-connected graph to a $k$-connected graph
    Lecture Notes in Computer Science, Springer-Verlag, vol. 1851, 7th Scandinavian Workshop on Algorithm Theory, SWAT'00 pp.286-299 2000年 [査読無し][通常論文]
  • T. Ishii and H. Nagamochi: Simultaneous augmentation of two graphs to an $\ell$-edge-connected graph and a biconnected graph
    Lecture Notes in Computer Science, vol.1969, Springer-Verlag, 11th Annual International Symposium on Algorithms and Computation, ISAAC'00 pp.326-337 2000年 [査読無し][通常論文]

受賞

  • 2016年03月 情報処理学会 山下記念研究賞
     
    受賞者: 石井 利昌
  • 2015年09月 FIT 船井ベストペーパー賞
     
    受賞者: 石井 利昌;牧野 和久
  • 2007年03月 日本オペレーションズ・リサーチ学会 文献賞奨励賞
     
    受賞者: 石井 利昌

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

教育活動情報

主要な担当授業

  • 論文
    開講年度 : 2018年
    課程区分 : 修士課程
    開講学部 : 経済学院
  • オペレーションズ・リサーチ特論A
    開講年度 : 2018年
    課程区分 : 修士課程
    開講学部 : 経済学院
    キーワード : 数理計画法,線形計画法, 整数計画法,ネットワーク計画法,動的計画法,非線形計画法
  • 現代経済経営演習Ⅰ
    開講年度 : 2018年
    課程区分 : 修士課程
    開講学部 : 経済学院
  • オペレーションズ・リサーチ特論B
    開講年度 : 2018年
    課程区分 : 修士課程
    開講学部 : 経済学院
    キーワード : 数理計画法,線形計画問題,凸計画問題, 非線形計画問題,整数計画問題
  • 現代経済経営演習Ⅱ
    開講年度 : 2018年
    課程区分 : 修士課程
    開講学部 : 経済学院
  • オペレーションズ・リサーチⅠ
    開講年度 : 2018年
    課程区分 : 学士課程
    開講学部 : 経済学部
    キーワード : 線形計画法,整数計画法,動的計画法,グラフ・ネットワーク
  • 現代経済経営演習
    開講年度 : 2018年
    課程区分 : 博士後期課程
    開講学部 : 経済学研究科
  • 演習Ⅰ(2単位)
    開講年度 : 2018年
    課程区分 : 学士課程
    開講学部 : 経済学部
    キーワード : オペレーションズ・リサーチ,数理計画,組合せ最適化,グラフ・ネットワーク,アルゴリズム
  • 現代経済経営演習
    開講年度 : 2018年
    課程区分 : 博士後期課程
    開講学部 : 経済学院
  • 卒業論文
    開講年度 : 2018年
    課程区分 : 学士課程
    開講学部 : 経済学部
  • 演習Ⅰ(2単位)
    開講年度 : 2018年
    課程区分 : 学士課程
    開講学部 : 経済学部
  • 演習Ⅱ(2単位)
    開講年度 : 2018年
    課程区分 : 学士課程
    開講学部 : 経済学部
  • 演習Ⅲ(2単位)
    開講年度 : 2018年
    課程区分 : 学士課程
    開講学部 : 経済学部
  • 演習Ⅳ(2単位)
    開講年度 : 2018年
    課程区分 : 学士課程
    開講学部 : 経済学部
  • 演習Ⅴ(2単位)
    開講年度 : 2018年
    課程区分 : 学士課程
    開講学部 : 経済学部
  • 演習Ⅵ(2単位)
    開講年度 : 2018年
    課程区分 : 学士課程
    開講学部 : 経済学部
  • 演習Ⅶ(2単位)
    開講年度 : 2018年
    課程区分 : 学士課程
    開講学部 : 経済学部
  • 演習Ⅷ(2単位)
    開講年度 : 2018年
    課程区分 : 学士課程
    開講学部 : 経済学部


Copyright © MEDIA FUSION Co.,Ltd. All rights reserved.