研究者データベース

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

基本情報

所属

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

職名

  • 教授

学位

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

ホームページ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
    Algorithmica 84 4 1107 - 1131 2022年 [査読有り]
  • Hitoshi Hayakawa, Toshimasa Ishii, Hirotaka Ono, Yushi Uno
    Discret. Appl. Math. 265 86 - 103 2019年 [査読有り]
  • Hitoshi Hayakawa, Toshimasa Ishii, Hirotaka Ono, Yushi Uno
    28th International Symposium on Algorithms and Computation, ISAAC 2017, December 9-12, 2017, Phuket, Thailand 46:1-46:13  Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik 2017年 [査読有り][通常論文]
  • 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 IJNC Editorial Committee 2014年 [査読有り][通常論文]
     
    Distance constrained labeling problems, e.g., L(p,q)-labeling and (p,q)-total labeling, are originally motivated by the frequency assignment. From the viewpoint of theory, the upper bounds on the labeling numbers and the time complexity of finding a minimum labeling are intensively and extensively studied. In this paper, we survey the distance constrained labeling problems from algorithmic aspects, that is, computational complexity, approximability, exact computation, and so on.
  • 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年 [査読有り][通常論文]
  • Toru Hasunuma, Toshimasa Ishii, Hirotaka Ono, Yushi Uno
    Combinatorial Algorithms - 21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010, Revised Selected Papers 6460 103 - + Springer 2011年 [査読有り][通常論文]
     
    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 If - f (y)vertical bar >= 2 if x is a vertex and y is an edge incident to x, and If - f(y)vertical bar >= 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) boolean OR E(G). The (2, 1)-total labeling number 4(G) of G is defined as the minimum k among all possible assignments. In [D. Chen and W. Wang. (2,I)-Total labelling of outerplanar graphs. Discr. Appl. Math. 155 (2007)], it was conjectured that all outerplanar graphs G satisfy lambda(T)(2)(G) <= Delta(G)+2, where Delta(G) is the maximum degree of G, while they also showed that it is true for G with Delta(G) >= 5. In this paper, we solve their conjecture completely, by proving that lambda(T)(2)(G) <= Delta(G) + 2 even in the case of Delta(G) <= 4.
  • 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
    ALGORITHMS AND COMPUTATION, PT 2 6507 49 - + 2010年 [査読有り][通常論文]
     
    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 vertical bar f (x)-f(y)vertical bar >= p if x is a vertex and y is an edge incident to x, and vertical bar f (x) - f (y)vertical bar >= 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) U E(G) -> {0, ..., k}, and the (p,q)-total labeling problem asks the minimum k, which we denote by lambda(T)(p,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 give a complete characterization of trees achieving lambda(T)(p,q)(T) if in addition Delta >= 4 holds, 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.
  • 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, PROCEEDINGS 5878 473 - + 2009年 [査読有り][通常論文]
     
    Given a system (V, f, r) on a finite set V consisting of a posi-modular function f : 2(V) -> R and a modulotone function r : 2(V) -> R we consider the problem of finding a minimum set R subset of V such that f(X) >= r(X) for all X subset of 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 pi-monotone, where a modulotone function r is pi-monotone if there exists a permutation pi of V such that the function p(r) : V x 2(V) R associated with r satisfies p(r)(u, W) >= p(r)(v, W) for all W subset of V and u, v is an element of V with pi(u) >= pi(v). Here we show that any modulotone function r can be characterized by p(r) as r(X) = max{p(r)(v,W) vertical bar v is an element of X subset of V - W}. We also show the structural properties on the minimal deficient sets W for the transversal problem for pi-monotone function r, i.e., there exists a basic tree T for W such that pi(u) <= pi(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.
  • Toru Hasunuma, Toshimasa Ishii, Hirotaka Ono, Yushi Uno
    ALGORITHMS - ESA 2009, PROCEEDINGS 5757 35 - + 2009年 [査読有り][通常論文]
     
    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 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 : V(G) --> {0, ... , k}, and the L(2, 1)-labeling problem asks the minimum k, which we denote by lambda(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(Delta(4.5)n) for more than a decade, and an O(min{n(1.75), Delta(1.5)n})-time algorithm has appeared recently, where Delta 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.
  • 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 5124 185 - + 2008年 [査読有り][通常論文]
     
    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 \ftx) - f(y)\ >= 2 if x and y are adjacent and If(x) - f(y)l I if x and y are at distance 2 for all x and y in V(G). A k-L(2, 1)-labeling is an assignment f : V(G) --> {0,...,k}, and the L(2, I)-labeling problem asks the minimum k, which we denote by lambda(G), among all possible assignments. 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 = \V(T)\. 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 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.
  • 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 4835 29 - + 2007年 [査読有り][通常論文]
     
    Let G = (V, E) be a simple undirected graph with a set V of vertices and a set E of edges. Each vertex v is an element of V has a demand d(v) is an element of Z(+), and a cost c(v) is an element of 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 Sigma(v is an element of S) c(v) such that there are at least d(v) pairwise vertex-disjoint paths from S to v for each vertex v is an element of V - S. It is known that the problem is not approximable within a ratio of O(1n Sigma(v is an element of V) d(v)), unless NP has an O(N-log (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) vertical bar v is an element of V}. In this paper, we consider the problem in the case where every vertex has a uniform cost. We propose a simple greedy algorithm for delivering a rnax f d* + 1, 2d* - 6}-approximate solution to the problem in O(min{d*, root vertical bar V vertical bar}d*vertical bar V vertical bar(2)) time. 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.
  • 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.
  • Ishii Toshimasa, Nagamochi Hiroshi, Ibaraki Toshihide
    Algorithmica 44 3 257 - 280 Springer-Verlag 2006年03月 [査読有り]
  • Hiroshi Nagamochi, Kengo Iwata, Toshimasa Ishii
    Theoretical Computer Science 341 1-3 364 - 378 2005年09月 [査読有り]
  • 石井 利昌, 永持 仁, 西垣 豊, 高橋 健吾, 武田 真人
    システム/制御/情報 : システム制御情報学会誌 = Systems, control and information 49 6 213 - 221 システム制御情報学会 2005年06月 [査読有り][通常論文]
     
    In the petrochemical industry, we have been required to optimize a production schedule for the efficient management. Determining how to provide naphtha to the petrochemical plant is one of the most crucial problems in the optimization of such production scheduling. Typically, purchased naphtha, which is provided from the sea berth, is first stored temporarily in storage tanks, and after that, is provided to the plant, according to a predetermined production schedule. Then we are required to find pairwise disjoint routes between the sea berth and a tank, between two distinct tanks, or between a tank and the plant. In this paper, we formulate the problem of finding routes in a tank network as a problem of computing disjoint paths in a graph, and propose an algorithm for enumerating all sets of disjoint paths based on the graph theory. Our algorithm first constructs a tree-shaped data structure for each pair of prescribed vertices which represents all paths between the pair of vertices, and then computes disjoint paths efficiently by traversing the tree-shaped data structures. We also evaluate the practical performance of our algorithm by conducting a computational experiment based on the case in Showa Denko K.K.
  • Toshimasa Ishii, Kengo Iwata, Hiroshi 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年 [査読有り][通常論文]
  • Hiroshi Nagamochi, Takahisa Suzuki, Toshimasa Ishii
    Information Processing Letters 89 5 223 - 226 2004年03月 [査読有り][通常論文]
  • Hiroshi Nagamochi, Toshimasa Ishii
    Discrete Applied Mathematics 129 2-3 475 - 486 2003年08月 [査読有り][通常論文]
  • Toshimasa Ishii, Yoko Akiyama, Hiroshi Nagamochi
    Electronic Notes in Theoretical Computer Science 78 243 - 266 2003年04月 [査読有り][通常論文]
     
    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 μ and W for every pair of a vertex μ ∈ 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 (k3 + n2)(p + kn + n logn) logk + pkn3 log(n/k)) time, where n = |V|, m = |{{u,v}|(u, v) ∈ E}|, and p = |W|.
  • Hiroshi Nagamochi, Shuji Nakamura, Toshimasa Ishii
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS E86D 2 179 - 185 2003年02月 [査読有り][通常論文]
     
    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 O(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 O(mn + n(2) log n) time and O(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.
  • Toshimasa Ishii, Hitoshi Fujita, Hiroshi Nagamochi
    Proceedings of the 3rd Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications pp.368-377 2003年 [査読有り][通常論文]
  • Toshimasa Ishii, Masayuki 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.
  • Toshimasa Ishii, Shigeyuki Yamamoto, Hiroshi 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.
  • Hiroshi Nagamochi, Toshimasa Ishii, Hiro Ito
    Information Processing Letters 80 6 287 - 293 2001年12月 [査読有り][通常論文]
  • Ishii Toshimasa, Nagamochi Hiroshi, Ibaraki Toshihide
    Networks 37 3 144 - 155 John Wiley & Sons, Ltd. 2001年05月 [査読有り][通常論文]
  • Hiroshi Nagamochi, Toshimasa Ishii
    Algorithms and Computation 124 - 135 2001年 [査読有り]
  • Toshimasa Ishii, Hiroshi Nagamochi
    Algorithm Theory - SWAT 2000 pp.286-299 286 - 299 2000年 [査読有り][通常論文]
  • Toshimasa Ishii, Hiroshi Nagamochi
    Algorithms and Computation pp.326-337 326 - 337 2000年 [査読有り][通常論文]
  • Ishii Toshimasa, Nagamochi Hiroshi, Ibaraki Toshihide
    Journal of Combinatorial Optimization 4 1 35 - 77 Kluwer Academic Publishers 2000年 [査読有り][通常論文]
  • Hiroshi Nagamochi, Toshimasa Ishii, Toshihide 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.
  • 石井 利昌, 永持 仁, 茨木 俊秀
    日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集 1999 414 - 425 公益社団法人日本オペレーションズ・リサーチ学会 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年 [査読有り][通常論文]
  • Toshimasa Ishii, Hiroshi Nagamochi, Toshihide Ibaraki
    Algorithms and Computation 159 - 169 1998年 [査読有り]
  • Ishii Toshimasa, Nagamochi Hiroshi, Ibaraki Toshihide
    Algorithms and Computation 102 - 111 1997年 [査読有り]

書籍

その他活動・業績

  • Toshimasa Ishii, Jun Kawahara, Kazuhisa Makino, Hirotaka Ono CoRR abs/2111.02579 2021年
  • 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.
  • 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.
  • Toshimasa Ishii, Kazuhisa Makino CoRR abs/1410.6030 2014年 [査読無し][通常論文]
  • 蓮沼 徹, 石井 利昌, 小野 廣隆, 宇野 裕之 研究報告アルゴリズム(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.
  • Toru Hasunuma, Toshimasa Ishii, Hirotaka Ono, Yushi Uno CoRR abs/0911.4590 2009年 [査読無し][通常論文]
  • 蓮沼徹, 石井利昌, 小野廣隆, 宇野裕之 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集 2008 308 -309 2008年09月10日 [査読無し][通常論文]
  • 蓮沼 徹, 石井 利昌, 小野 廣隆, 宇野 裕之 情報科学技術フォーラム講演論文集 7 (1) 5 -6 2008年08月20日
  • 蓮沼徹, 石井利昌, 小野廣隆, 宇野裕之 電子情報通信学会技術研究報告. 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日
  • 萩原 正之, 石井 利昌, 永持 仁 電子情報通信学会技術研究報告. 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以内の解が見つかることを示す。
  • 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.
  • 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年 [査読無し][通常論文]
  • 石井 利昌, 秋山 容子, 永持 仁 電子情報通信学会技術研究報告. 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|である.
  • 永持 仁, 阿部 勇介, 石井 利昌 数理解析研究所講究録 1241 157 -165 2001年12月
  • 永持 仁, 中村 秀司, 石井 利昌 数理解析研究所講究録 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倍以下の解を線形時間で出力するアルゴリズムを与える.
  • 永持 仁, 石井 利昌 電子情報通信学会総合大会講演論文集 2001 (1) 316 -317 2001年03月07日
  • 石井 利昌, 永持 仁, 茨木 俊秀 電子情報通信学会技術研究報告. COMP, コンピュテーション 99 (30) 41 -48 1999年04月23日 
    辺連結度, 点連結度を同時に最適増大させる問題とは, 入力として, 無向多重グラフG=(V, E)と, 2つの正整数k,l が与えられたとき, 最小本数の辺をGに加えることで, グラフの辺連結度および点連結度をそれぞれk以上, かつl以上にする問題である. 本研究では, 入力グラフが(l-1)-点連結グラフ(l4)である場合, この問題に対して, 最適解との差が2k以下である近似解を出力する多項式時間アルゴリズムを構築する.
  • 石井 利昌, 永持仁, 茨木 俊秀 情報処理学会研究報告アルゴリズム(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.
  • 石井 利昌, 永持 仁, 茨木 俊秀 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集 1997 262 -263 1997年09月10日
  • 石井 利昌, 永持 仁, 茨木 俊秀 日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集 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.
  • 永持 仁, 石井 利昌, 茨木 俊秀 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集 1995 150 -151 1995年10月16日
  • 永持 仁, 石井 利昌, 茨木 俊秀 電子情報通信学会技術研究報告. 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の場合)の多項式時間アルゴリズムを構築する.

受賞

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

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

教育活動情報

主要な担当授業

  • オペレーションズ・リサーチ特論A
    開講年度 : 2021年
    課程区分 : 修士課程
    開講学部 : 経済学院
    キーワード : 数理計画法,線形計画法, 整数計画法,ネットワーク計画法,動的計画法,非線形計画法
  • オペレーションズ・リサーチ特論B
    開講年度 : 2021年
    課程区分 : 修士課程
    開講学部 : 経済学院
    キーワード : 数理計画,線形計画,整数計画, 組合せ最適化
  • 現代経済経営演習Ⅰ
    開講年度 : 2021年
    課程区分 : 修士課程
    開講学部 : 経済学院
    キーワード : オペレーションズ・リサーチ,数理計画,組合せ最適化,グラフ・ネットワーク,アルゴリズム
  • 現代経済経営演習Ⅱ
    開講年度 : 2021年
    課程区分 : 修士課程
    開講学部 : 経済学院
    キーワード : オペレーションズ・リサーチ,数理計画,組合せ最適化,グラフ・ネットワーク,アルゴリズム
  • オペレーションズ・リサーチⅠ
    開講年度 : 2021年
    課程区分 : 学士課程
    開講学部 : 経済学部
    キーワード : 線形計画法,整数計画法,動的計画法,グラフ・ネットワーク
  • 演習Ⅰ(2単位)
    開講年度 : 2021年
    課程区分 : 学士課程
    開講学部 : 経済学部
    キーワード : オペレーションズ・リサーチ,数理計画,組合せ最適化,グラフ・ネットワーク,アルゴリズム
  • 演習Ⅱ(2単位)
    開講年度 : 2021年
    課程区分 : 学士課程
    開講学部 : 経済学部
    キーワード : オペレーションズ・リサーチ,数理計画,組合せ最適化,グラフ・ネットワーク,アルゴリズム
  • 演習Ⅲ(2単位)
    開講年度 : 2021年
    課程区分 : 学士課程
    開講学部 : 経済学部
    キーワード : オペレーションズ・リサーチ,数理計画,組合せ最適化,グラフ・ネットワーク,アルゴリズム
  • 演習Ⅳ(2単位)
    開講年度 : 2021年
    課程区分 : 学士課程
    開講学部 : 経済学部
    キーワード : オペレーションズ・リサーチ,数理計画,組合せ最適化,グラフ・ネットワーク,アルゴリズム
  • 演習Ⅴ(2単位)
    開講年度 : 2021年
    課程区分 : 学士課程
    開講学部 : 経済学部
    キーワード : オペレーションズ・リサーチ,数理計画,組合せ最適化,グラフ・ネットワーク,アルゴリズム
  • 演習Ⅵ(2単位)
    開講年度 : 2021年
    課程区分 : 学士課程
    開講学部 : 経済学部
    キーワード : オペレーションズ・リサーチ,数理計画,組合せ最適化,グラフ・ネットワーク,アルゴリズム
  • 演習Ⅶ(2単位)
    開講年度 : 2021年
    課程区分 : 学士課程
    開講学部 : 経済学部
    キーワード : オペレーションズ・リサーチ,数理計画,組合せ最適化,グラフ・ネットワーク,アルゴリズム
  • 演習Ⅷ(2単位)
    開講年度 : 2021年
    課程区分 : 学士課程
    開講学部 : 経済学部
    キーワード : オペレーションズ・リサーチ,数理計画,組合せ最適化,グラフ・ネットワーク,アルゴリズム
  • 現代日本制度ⅠD
    開講年度 : 2021年
    課程区分 : 学士課程
    開講学部 : 現代日本学プログラム課程
    キーワード : 線形計画法,整数計画法,動的計画法,グラフ・ネットワーク
  • 統計学
    開講年度 : 2021年
    課程区分 : 学士課程
    開講学部 : 全学教育
    キーワード : 平均,分散,標準偏差,確率変数,確率分布,母集団,標本,標本分布,点推定,信頼区間,仮説検定
  • 企業情報システム
    開講年度 : 2021年
    課程区分 : 専門職大学院
    開講学部 : 経済学院
    キーワード : 数理計画法,線形計画法, 整数計画法,ネットワーク計画法,動的計画法,非線形計画法


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