伊藤 大雄
| 情報・ネットワーク工学専攻 | 教授 |
| Ⅰ類（情報系） | 教授 |
研究者情報
経歴
- 2012年04月01日
電気通信大学 大学院 情報理工学研究科, 教授 - 2001年06月01日 - 2012年03月31日
京都大学 大学院 情報学研究科, 助教授(2007.3.31まで)～准教授 - 2006年06月12日 - 2006年09月30日
Department of Computer Science, The University of Warwick, 客員研究員 - 1996年04月01日 - 2001年05月31日
豊橋技術科学大学 情報工学系, 講師 - 1995年03月01日 - 1996年03月31日
日本電信電話株式会社 通信網研究所, 主任研究員 - 1990年02月01日
日本電信電話株式会社 通信網総合研究所, 研究主任 - 1987年04月01日
日本電信電話株式会社 基礎研究所
研究活動情報
論文
- Multifold tiles of polyominoes and convex lattice polygons
Kota Chida; Erik D. Demaine; Martin L. Demaine; David Eppstein; Adam Hesterberg; Takashi Horiyama; John Iacono; Hiro Ito; Stefan Langerman; Ryuhei Uehara; Yushi Uno
責任著者, Thai Journal of Mathematics, 出版日 2023年, 査読付
研究論文（学術雑誌）, 英語 - Computational complexity of flattening fixed-angle orthogonal chains
Erik D. Demaine; Hiro Ito; Jayson Lynch; Ryuhei Uehara
Proceedings of The 34th Canadian Conference on Computational Geometry, online巻, 掲載ページ 1-7, 出版日 2022年08月, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Sublinear computation paradigm: constant-time algorithms and sublinear progressive algorithms
Kyohei Chiba; Hiro Ito
責任著者, IEICE Transactions, 105-A巻, 3号, 出版日 2022年03月, 査読付
研究論文（学術雑誌）, 英語 - Turning Around and Around: Motion Planning through Thick and Thin Turnstiles
Aster Greenblatt; Oscar Hernandez; Robert A. Hearn; Yichao Hou; Hiro Ito; Minwoo Joshua Kang; Aaron Williams; Andrew Winslow
Proceedings of The 33rd Canadian Conference on Computational Geometry (CCCG2021), published online巻, 掲載ページ 377-387, 出版日 2021年07月, 査読付
研究論文（国際会議プロシーディングス）, 英語 - On the characterization of 1-sided error strongly-testable graph properties for bounded-degree graphs
Hiro Ito; Areej Khoury; Ilan Newman
Journal of Computational Complexity, Springer, 29巻, Article 1号, 掲載ページ 1-45, 出版日 2020年, 査読付
研究論文（学術雑誌）, 英語 - Generalized shogi, chess, and xiangqui are constant-time testable
ITO Hiro; NAGAO Atsuki; PARK Teagun
IEICE Transactions, E102-A巻, 9号, 掲載ページ 1126-1133, 出版日 2019年09月, 査読付
研究論文（学術雑誌）, 英語 - Preface for the Special Issue on the Project "Foundation of Innovative Algorithms for Big Data".
Naoki Katoh; Yuya Higashikawa; Hiro Ito; Shun Kataoka; Takuya Kida; Toshiki Saitoh; Tetsuo Shibuya; Kazuyuki Tanaka; Yushi Uno
Rev. Socionetwork Strateg., 13巻, 2号, 掲載ページ 99-100, 出版日 2019年
研究論文（学術雑誌） - Cookie Clicker
Erik D. Demaine; Hiro Ito; Stefan Langerman; Jayson Lynch; Mikhail Rudoy; Kai Xiao
Graphs and Combinatorics, 未定巻, 出版日 2019年, 査読付
研究論文（学術雑誌）, 英語 - What graph properties are constant-time testable? --- dense graphs, sparse graphs, and complex networks
ITO Hiro
The Review of Socionetwork Strategies, Springer, 13巻, 2号, 掲載ページ 101-121, 出版日 2019年, 査読付, 招待
研究論文（学術雑誌）, 英語 - Energy efficiency and renewable energy management with multi-state power-down system
James Andro-Vasko; Wolfgang Bein; Hiro Ito
Information, 10巻, 2号, 掲載ページ 44:1-44:21, 出版日 2018年12月, 査読付
研究論文（学術雑誌）, 英語 - A heuristic for state power down systems with few states
James Andro-Vasko; Wolfgang Bein; Hiro Ito; Govind Pathak
Advances in Intelligent Systems and Computing, Springer Verlag, 558巻, 掲載ページ 877-882, 出版日 2018年, 査読付, Power-down mechanisms are well known and are widely used to save energy. We consider a device which has states OFF, ON, and a fixed number of intermediate states. The state of the device can be switched at any time. In the OFF state the device consumes zero energy and in ON state it works at its full power consumption. The intermediate states consume only some fraction of energy proportional to the usage time but switching back to the ON state has different constant setup cost depending on the current state. We give a new heuristic to construct optimal power-down systems with few states. The heuristic converges very quickly to an optimal solution.
研究論文（国際会議プロシーディングス）, 英語 - Bumpy pyramid folding
Zachary R. Abel; Erik D. Demaine; Martin L. Demaine; Hiro Ito; Jack Snoeyink; Ryuhei Uehara
Computational Geometry: Theory and Applications, Elsevier B.V., 75巻, 掲載ページ 22-31, 出版日 2018年, 査読付, We investigate folding problems for a class of petal (or star-like) polygons P, which have an n-polygonal base B surrounded by a sequence of triangles for which adjacent pairs of sides have equal length. We give linear time algorithms using constant precision to determine if P can fold to a pyramid with flat base B, and to determine a triangulation of B (crease pattern) that allows folding into a convex (triangulated) polyhedron. By Alexandrov's Theorem, the crease pattern is unique if it exists, but the general algorithm known for this theorem is pseudo-polynomial, with running time O(n456.5)
ours is the first efficient algorithm for Alexandrov's Theorem for a special class of polyhedra. We also give a polynomial time algorithm that finds the crease pattern to produce the maximum volume triangulated polyhedron.
研究論文（学術雑誌）, 英語 - A much faster algorithm for finding a maximum clique with computational experiments
Etsuji Tomita; Sora Matsuzaki; Atsuki Nagao; Hiro Ito; Mitsuo Wakatsuki
Journal of Information Processing, Information Processing Society of Japan, 25巻, 8号, 掲載ページ 667-677, 出版日 2017年08月01日, 査読付, We present further improvements to a branch-and-bound maximum-clique-finding algorithm MCS (WALCOM 2010, LNCS 5942, pp.191-203) that was shown to be fast. First, we employ a variant of an efficient approximation algorithm KLS for finding a maximum clique. Second, we make use of appropriate sorting of vertices only near the root of the search tree. Third, we employ a lightened approximate coloring mainly near the leaves of the search tree. A new algorithm obtained from MCS with the above improvements is named k5_MCT. It is shown that k5_MCT is much faster than MCS by extensive computational experiments. In particular, k5_MCT is shown to be faster than MCS for gen400 p0.9 75, gen400 p0.9 65 and gen400 p0.9 55 by over 81,000, 39,000 and 19,000 times, respectively.
研究論文（学術雑誌）, 英語 - Unfolding and dissection of multiple cubes, tetrahedra, and doubly covered squares
Zachary Abel; Brad Ballinger; Erik D. Demaine; Martin L. Demaine; Jeff Erickson; Adam Hesterberg; Hiro Ito; Irina Kostitsyna; Jayson Lynch; Ryuhei Uehara
Journal of Information Processing, Information Processing Society of Japan, 25巻, 8号, 掲載ページ 610-615, 出版日 2017年08月01日, 査読付, In this paper, we introduce the notion of “rep-cube”: a net of a cube that can be divided into multiple polygons, each of which can be folded into a cube. This notion is inspired by the notion of polyomino and rep-tile
both are introduced by SolomonW. Golomb, and well investigated in the recreational mathematics society. We prove that there are infinitely many distinct rep-cubes. We also extend this notion to doubly covered squares and regular tetrahedra.
研究論文（学術雑誌）, 英語 - Transforming graphs with the same graphic sequence
Sergey Bereg; Hiro Ito
Journal of Information Processing, Information Processing Society of Japan, 25巻, 8号, 掲載ページ 627-633, 出版日 2017年08月01日, 査読付, Let G and H be two graphs with the same vertex set V. It is well known that a graph G can be transformed into a graph H by a sequence of 2-switches if and only if every vertex of V has the same degree in both G and H. We study the problem of finding the minimum number of 2-switches for transforming G into H.
研究論文（学術雑誌）, 英語 - How to solve the cake-cutting problem in sublinear time
Hiro Ito; Takahiro Ueda
Leibniz International Proceedings in Informatics, LIPIcs, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 49巻, 出版日 2016年06月01日, 査読付, The cake-cutting problem refers to the issue of dividing a cake into pieces and distributing them to players who have different value measures related to the cake, and who feel that their portions should be "fair." The fairness criterion specifies that in situations where n is the number of players, each player should receive his/her portion with at least 1/n of the cake value in his/her measure. In this paper, we show algorithms for solving the cake-cutting problem in sublinear-time. More specifically, we preassign fair portions to o(n) players in o(n)-time, and minimize the damage to the rest of the players. All currently known algorithms require Ω(n)-time, even when assigning a portion to just one player, and it is nontrivial to revise these algorithms to run in o(n)-time since many of the remaining players, who have not been asked any queries, may not be satisfied with the remaining cake. To challenge this problem, we begin by providing a framework for solving the cake-cutting problem in sublinear-time. Generally speaking, solving a problem in sublinear-time requires the use of approximations. However, in our framework, we introduce the concept of "ϵn-victims," which means that ϵn players (victims) may not get fair portions, where 0 <
ϵ ≤ 1 is an arbitrary constant. In our framework, an algorithm consists of the following two parts: In the first (Preassigning) part, it distributes fair portions to r <
n players in o(n)-time. In the second (Completion) part, it distributes fair portions to the remaining n - r players except for the ϵn victims in poly(n)-time. There are two variations on the r players in the first part. Specifically, whether they can or cannot be designated. We will then present algorithms in this framework. In particular, an O(r/ϵ)-time algorithm for r ≤ ϵn/127 undesignated players with ϵn-victims, and an Õ(r2/ϵ)-time algorithm for r ≤ ϵe√ln n/7 designated players and ϵ ≤ 1/e with ϵn-victims are presented.
研究論文（国際会議プロシーディングス）, 英語 - A Much Faster Branch-and-Bound Algorithm for Finding a Maximum Clique
Etsuji Tomita; Kohei Yoshida; Takuro Hatta; Atsuki Nagao; Hiro Ito; Mitsuo Wakatsuki
Frontiers in Algorithmics, FAW 2016, SPRINGER INT PUBLISHING AG, 9711巻, 掲載ページ 215-226, 出版日 2016年, 査読付, We present improvements to a branch-and-bound maximum-clique-finding algorithm MCS (WALCOM 2010, LNCS 5942, pp. 191-203) that was shown to be fast. First, we employ an efficient approximation algorithm for finding a maximum clique. Second, we make use of appropriate sorting of vertices only near the root of the search tree. Third, we employ a lightened approximate coloring mainly near the leaves of the search tree. A new algorithm obtained from MCS with the above improvements is named MCT. It is shown that MCT is much faster than MCS by extensive computational experiments. In particular, MCT is shown to be faster than MCS for gen400_p0.9_75 and gen400_p0.9_65 by over 328,000 and 77,000 times, respectively.
研究論文（国際会議プロシーディングス）, 英語 - Folding a paper strip to minimize thickness
Erik D. Demaine; David Eppstein; Adam Hesterberg; Hiro Ito; Anna Lubiw; Ryuhei Uehara; Yushi Uno
Journal of Discrete Algorithms, Elsevier, 36巻, 掲載ページ 18-26, 出版日 2016年01月01日, 査読付, In this paper, we study how to fold a specified origami crease pattern in order to minimize the impact of paper thickness. Specifically, origami designs are often expressed by a mountain-valley pattern (plane graph of creases with relative fold orientations), but in general this specification is consistent with exponentially many possible folded states. We analyze the complexity of finding the best consistent folded state according to two metrics: minimizing the total number of layers in the folded state (so that a "flat folding" is indeed close to flat), and minimizing the total amount of paper required to execute the folding (where "thicker" creases consume more paper). We prove both problems strongly NP-complete even for 1D folding. On the other hand, we prove both problems fixed-parameter tractable in 1D with respect to the number of layers.
研究論文（国際会議プロシーディングス）, 英語 - Number of Ties and Undefeated Signs in a Generalized Janken
Hiro Ito; Yoshinao Shiono
DISCRETE AND COMPUTATIONAL GEOMETRY AND GRAPHS, JCDCGG 2015, SPRINGER INT PUBLISHING AG, 9943巻, 掲載ページ 143-154, 出版日 2016年, 査読付, Janken, which is a very simple game and is usually used as a coin-toss in Japan, originated in China, and many variants are seen throughout the world. A variant of janken can be represented by a tournament (a complete asymmetric digraph), where a vertex corresponds to a sign and an arc (x, y) indicates that sign x defeats sign y. However, not all tournaments define useful janken variants, i.e., some janken variants may include a useless sign, which is strictly inferior to any other sign in any case. In a previous paper by one of the authors, a variant of janken (or simply janken) was said to be efficient if it contains no such useless signs, and some properties of efficient jankens were presented. The jankens considered in the above research had no tie between different signs. However, some actual jankens do include such ties. In the present paper, we investigate jankens that are allowed to have a tie between different signs. That is, a janken can be represented as an asymmetric digraph, where no edge between two vertices x and y indicates a tie between x and y. We first show the tight upper and lower bounds of the number of ties in an efficient janken with n-vertices. Moreover, it is shown that for any integer t between the upper and lower bounds, there is an efficient janken having just t ties. We next consider undefeated vertices, which are vertices that are not defeated by any sign. We show that there is an efficient janken with n vertices such that the number of vertices that are not undefeated is o(n), i.e., almost all vertices are undefeated.
研究論文（国際会議プロシーディングス）, 英語 - Single-Player and Two-Player Buttons & Scissors Games
Kyle Burke; Erik D. Demaine; Harrison Gregg; Robert A. Hearn; Adam Hesterberg; Michael Hoffmann; Hiro Ito; Irina Kostitsyna; Jody Leonard; Maarten Loeffler; Aaron Santiago; Christiane Schmidt; Ryuhei Uehara; Yushi Uno; Aaron Williams
DISCRETE AND COMPUTATIONAL GEOMETRY AND GRAPHS, JCDCGG 2015, SPRINGER INT PUBLISHING AG, 9943巻, 掲載ページ 60-72, 出版日 2016年, 査読付, We study the computational complexity of the Buttons & Scissors game and obtain sharp thresholds with respect to several parameters. Specifically we show that the game is NP-complete for C = 2 colors but polytime solvable for C = 1. Similarly the game is NP-complete if every color is used by at most F = 4 buttons but polytime solvable for F <= 3. We also consider restrictions on the board size, cut directions, and cut sizes. Finally, we introduce several natural two-player versions of the game and show that they are PSPACE-complete.
研究論文（国際会議プロシーディングス）, 英語 - Every property is testable on a natural class of scale-free multigraphs
Hiro ITO
Proceedings of the 24th European Symposium of Algorithms (ESA 2016), LIPICS, 57巻, 掲載ページ 51:1-51:12, 出版日 2016年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Constant-time algorithms for complex networks
Hiro ITO
Proceedings of the Asia-Pacific World Congress on Computer Science 2016 (APWConCS2016), to appear巻, 出版日 2016年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Single-Player and Two-Player Buttons & Scissors Games
Kyle Burke; Erik D. Demaine; Harrison Gregg; Robert A. Hearn; Adam Hesterberg; Michael Hoffmann; Hiro Ito; Irina Kostitsyna; Jody Leonard; Maarten Loeffler; Aaron Santiago; Christiane Schmidt; Ryuhei Uehara; Yushi Uno; Aaron Williams
DISCRETE AND COMPUTATIONAL GEOMETRY AND GRAPHS, JCDCGG 2015, SPRINGER INT PUBLISHING AG, 9943巻, 掲載ページ 60-72, 出版日 2016年, 査読付, We study the computational complexity of the Buttons & Scissors game and obtain sharp thresholds with respect to several parameters. Specifically we show that the game is NP-complete for C = 2 colors but polytime solvable for C = 1. Similarly the game is NP-complete if every color is used by at most F = 4 buttons but polytime solvable for F <= 3. We also consider restrictions on the board size, cut directions, and cut sizes. Finally, we introduce several natural two-player versions of the game and show that they are PSPACE-complete.
研究論文（国際会議プロシーディングス）, 英語 - Number of Ties and Undefeated Signs in a Generalized Janken
Hiro Ito; Yoshinao Shiono
DISCRETE AND COMPUTATIONAL GEOMETRY AND GRAPHS, JCDCGG 2015, SPRINGER INT PUBLISHING AG, 9943巻, 掲載ページ 143-154, 出版日 2016年, 査読付, Janken, which is a very simple game and is usually used as a coin-toss in Japan, originated in China, and many variants are seen throughout the world. A variant of janken can be represented by a tournament (a complete asymmetric digraph), where a vertex corresponds to a sign and an arc (x, y) indicates that sign x defeats sign y. However, not all tournaments define useful janken variants, i.e., some janken variants may include a useless sign, which is strictly inferior to any other sign in any case. In a previous paper by one of the authors, a variant of janken (or simply janken) was said to be efficient if it contains no such useless signs, and some properties of efficient jankens were presented. The jankens considered in the above research had no tie between different signs. However, some actual jankens do include such ties. In the present paper, we investigate jankens that are allowed to have a tie between different signs. That is, a janken can be represented as an asymmetric digraph, where no edge between two vertices x and y indicates a tie between x and y. We first show the tight upper and lower bounds of the number of ties in an efficient janken with n-vertices. Moreover, it is shown that for any integer t between the upper and lower bounds, there is an efficient janken having just t ties. We next consider undefeated vertices, which are vertices that are not defeated by any sign. We show that there is an efficient janken with n vertices such that the number of vertices that are not undefeated is o(n), i.e., almost all vertices are undefeated.
研究論文（国際会議プロシーディングス）, 英語 - Evaluation of Online Power-Down Algorithms
James Andro-Vasko; Wolfgang Bein; Dara Nyknahad; Hiro Ito
2015 12TH INTERNATIONAL CONFERENCE ON INFORMATION TECHNOLOGY - NEW GENERATIONS, IEEE, 掲載ページ 473-478, 出版日 2015年, 査読付, Power-down mechanisms are well known and are widely used to save energy; these mechanisms are encountered on an everyday basis. We consider a device which has states OFF, ON, and a fixed number of intermediate states. The state of the device can be switched at any time. In the OFF state the device consumes zero energy and in ON state it works at its full power consumption. The intermediate states consume only some fraction of energy proportional to the usage time but switching back to the ON state has different constant setup cost depending on the current state. We give results regarding power consumption to satisfy service request based on online competitive analysis. Competitive ratios, which show the effectiveness of the algorithms compared to the optimal solution, are calculated for systems with up to six states. For two state on-off systems, a decrease and reset algorithm is analyzed experimentally. It is shown that this algorithm has favorable performance for request sequences with high slackness degree.
研究論文（国際会議プロシーディングス）, 英語 - Cannibal Animal Games: A new variant of Tic-Tac-Toe
Jean Cardinal; Sébastien Collette; Hiro Ito; Matias Korman; Stefan Langerman; Hikaru Sakaidani; Perouz Taslakian
Journal of Information Processing, Information Processing Society of Japan, 23巻, 3号, 掲載ページ 265-271, 出版日 2015年, 査読付, This paper presents a new partial two-player game, called the cannibal animal game, which is a variant of Tic-Tac-Toe. The game is played on the infinite grid, where in each round a player chooses and occupies free cells. The first player Alice can occupy a cell in each turn and wins if she occupies a set of cells, the union of a subset of which is a translated, reflected and/or rotated copy of a previously agreed upon polyomino P (called an animal). The objective of the second player Bob is to prevent Alice from creating her animal by occupying in each round a translated, reflected and/or rotated copy of P. An animal is a cannibal if Bob has a winning strategy, and a non-cannibal otherwise. This paper presents some new tools, such as the bounding strategy and the punching lemma, to classify animals into cannibals or non-cannibals. We also show that the pairing strategy works for this problem.
研究論文（学術雑誌）, 英語 - Folding a Paper Strip to Minimizing Thickness
Erik D. DEMAINE; David EPPSTEIN; Adam HESTERBERG; Hiro ITO; Anna LUBIW; Ryuhei UEHARA; Yushi UNO
Proceeding of Workshop on Algorithms and Computation 2015 (WALCOM 2015), Springer, 8973巻, 掲載ページ 113-124, 出版日 2015年, 査読付, In this paper, we study how to fold a specified origami crease pattern in order to minimize the impact of paper thickness. Specifically, origami designs are often expressed by a mountain-valley pattern (plane graph of creases with relative fold orientations), but in general this specification is consistent with exponentially many possible folded states. We analyze the complexity of finding the best consistent folded state according to two metrics: minimizing the total number of layers in the folded state (so that a "flat folding" is indeed close to flat), and minimizing the total amount of paper required to execute the folding (where "thicker" creases consume more paper). We prove both problems strongly NPcomplete even for 1D folding. On the other hand, we prove both problems fixed-parameter tractable in 1D with respect to the number of layers.WALCOM: Algorithms and Computation, 9th International Workshop, WALCOM 2015, Dhaka, Bangladesh, February 26-28, 2015. Proceedings
研究論文（国際会議プロシーディングス）, 英語 - Generalized shogi and chess are constant-time tastable
Hiro ITO; Atsuki NAGAO; Teagun PARK
Proceedings of the 12th International Symposium on Operations Research & Its Applications (ISORA 2015), IET Digital Library, 掲載ページ 1-6, 出版日 2015年, 査読付, 招待
研究論文（国際会議プロシーディングス）, 英語 - Computational complexity of inverse word search problem
Hiro ITO; Shinnosuke SEKI
Proceedings of the 12th International Symposium on Operations Research & Its Applications (ISORA 2015), IET Digital Library, 掲載ページ 41-44, 出版日 2015年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Testing outerplanarity of bounded degree graphs
YOSHIDA Yuichi; ITO Hiro
Algorithmica, to appear巻, 出版日 2014年, 査読付
研究論文（学術雑誌）, 英語 - Generalized River Crossing Problems
Hiro Ito; Stefan Langerman; Yuichi Yoshida
Theory of Computing Systems, Springer New York LLC, 56巻, 2号, 掲載ページ 418-435, 出版日 2014年, 査読付, 招待, Three men, each with a sister, must cross a river using a boat that can carry only two people in such a way that a sister is never left in the company of another man if her brother is not present. This very famous problem appeared in the Latin book “Problems to Sharpen the Young,” one of the earliest collections of recreational mathematics. This paper considers a generalization of such “river crossing problems” and provides a new formulation that can treat wide variations. The main result is that, if there is no upper bound on the number of transportations (river crossings), a large class of subproblems can be solved in polynomial time even when the passenger capacity of the boat is arbitrarily large. The authors speculated this fact at FUN 2012. On the other hand, this paper also demonstrates that, if an upper bound on the number of transportations is given, the problem is NP-hard even when the boat capacity is three, although a large class of subproblems can be solved in polynomial time if the boat capacity is two.
研究論文（学術雑誌）, 英語 - On computational complexity of graph inference from counting
Szilárd Zsolt Fazekas; Hiro Ito; Yasushi Okuno; Shinnosuke Seki; Kei Taneishi
Natural Computing, 12巻, 4号, 掲載ページ 589-603, 出版日 2013年12月, 査読付, In de novo drug design, chemical compounds are quantitized as real-valued vectors called chemical descriptors, and an optimization algorithm runs on known drug-like chemical compounds in a database and outputs an optimal chemical descriptor. Since structural information is needed for chemical synthesis, we must infer chemical graphs from the obtained descriptor. This is formalized as a graph inference problem from a real-value vector. By generalizing subword history, which was originally introduced in formal language theory to extract numerical information of words and languages based on counting, we propose a comprehensive framework to investigate the computational complexity of chemical graph inference. We also propose a (pseudo-)polynomial-time algorithm for inferring graphs in a class of practical importance from spectrums. © 2012 Springer Science+Business Media Dordrecht.
研究論文（学術雑誌）, 英語 - Helly Numbers of Polyominoes
Jean Cardinal; Hiro Ito; Matias Korman; Stefan Langerman
Graphs and Combinatorics, 29巻, 5号, 掲載ページ 1221-1234, 出版日 2013年09月, 査読付, We define the Helly number of a polyomino P as the smallest number h such that the h-Helly property holds for the family of symmetric and translated copies of P on the integer grid. We prove the following: (i) the only polyominoes with Helly number 2 are the rectangles, (ii) there does not exist any polyomino with Helly number 3, (iii) there exist polyominoes of Helly number k for any k ≠ 1, 3. © 2012 Springer.
研究論文（学術雑誌）, 英語 - How to generalize janken - Rock-paper-scissors-king-flea
Hiro Ito
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer, 8296巻, 掲載ページ 85-94, 出版日 2013年, 査読付, Janken, which is a very simple game and it is usually used as a coin-toss in Japan, originated in China, and many variants are seen throughout the world. A variant of janken can be represented by a tournament, where a vertex corresponds a sign and an arc (x,y) means sign x defeats sign y. However, not all tournaments define useful janken variants, i.e., some janken variants may include a useless sign, which is strictly inferior than another sign in any case. We first shows that for any positive integer n except 2 and 4, we can construct a janken variant with n signs without useless signs. Next we introduces a measure of amusement of janken variants by using the variation of the difference of out-degree and in-degree. Under this measure, we show that a janken variant has the best amusement among ones with n signs if and only if it corresponds to one of the tournaments defined by J. W. Moon in 1993. Following these results, we present a janken variant "King-fles-janken," which is the best amusing janken variant among ones with five signs. © 2013 Springer-Verlag.
研究論文（国際会議プロシーディングス）, 英語 - Property Testing on k-Vertex-Connectivity of Graphs
Yuichi Yoshida; Hiro Ito
ALGORITHMICA, SPRINGER, 62巻, 3-4号, 掲載ページ 701-712, 出版日 2012年04月, 査読付, We present an algorithm for testing the k-vertex-connectivity of graphs with the given maximum degree. The time complexity of the algorithm is independent of the number of vertices and edges of graphs. Fixed degree bound d, a graph G with n vertices and a maximum degree at most d is called epsilon-far from k-vertexconnectivity when at least epsilon dn/2 dn 2 edges must be added to or removed from G to obtain a k-vertex-connected graph with a maximum degree at most d. The algorithm always accepts every graph that is k-vertex-connected and rejects every graph that is k-far from k-vertex-connectivity with a probability of at least 2/ 3. The algorithm runs in O(d(c/epsilon d) k log 1/epsilon d) time (c > 1 is a constant) for (k -1)-vertex-connected graphs, and in O(d(ck/epsilon d) k log k/epsilon d) time (c > 1 is a constant) for general graphs. It is the first constant-time k-vertex-connectivity testing algorithm for general k = 4.
研究論文（学術雑誌）, 英語 - An almost optimal algorithm for Winkler's sorting pairs in bins
Hiro Ito; Junichi Teruyama; Yuichi Yoshida
Progress in Informatics, 9号, 掲載ページ 3-7, 出版日 2012年03月, 査読付, We investigate the following sorting problem: We are given n bins with two balls in each bin. Balls in the ith bin are numbered n + 1 - i. We can swap two balls from adjacent bins. How many number of swaps are needed in order to sort balls, i.e., move every ball to the bin with the same number. For this problem the best known solution requires almost 4/5 n 2 swaps. In this paper, we show an algorithm which solves this problem using less than 2n 2/3 swaps. Since it is known that the lower bound of the number of swaps is ⌈(2n/2)/3⌉ = ⌈2n 2/3 - n/3⌉, our result is almost tight. Furthermore, we show that for n = 2 m + 1 (m ≥ 0) the algorithm is optimal. © 2012 National Institute of Informatics.
研究論文（学術雑誌）, 英語 - Constant-time approximation algorithms for the knapsack problem
Hiro Ito; Susumu Kiyoshima; Yuichi Yoshida
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7287巻, 7287号, 掲載ページ 131-142, 出版日 2012年, 査読付, In this paper, we give a constant-time approximation algorithm for the knapsack problem. Using weighted sampling, with which we can sample items with probability proportional to their profits, our algorithm runs with query complexity O(ε -4 logε -1), and it approximates the optimal profit with probability at least 2/3 up to error at most an ε-fraction of the total profit. For the subset sum problem, which is a special case of the knapsack problem, we can improve the query complexity to O(ε -1 logε -1). © 2012 Springer-Verlag.
研究論文（国際会議プロシーディングス）, 英語 - Algorithms and complexity of generalized river crossing problems
Hiro Ito; Stefan Langerman; Yuichi Yoshida
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7288巻, 7288号, 掲載ページ 235-244, 出版日 2012年, 査読付, Three men, each with a sister, must cross a river using a boat which can carry only two people, so that a woman whose brother is not present is never left in the company of another man. This is a very famous problem appeared in Latin book "Problems to Sharpen the Young," one of the earliest collections on recreational mathematics. This paper considers a generalization of such "River-Crossing Problems." It shows that the problem is NP-hard if the boat size is three, and a large class of sub-problems can be solved in polynomial time if the boat size is two. It's also conjectured that determining whether a river crossing problem has a solution without bounding the number of transportations, can be solved in polynomial time even when the size of the boat is large. © 2012 Springer-Verlag Berlin Heidelberg.
研究論文（国際会議プロシーディングス）, 英語 - Constant-Time Algorithms for Sparsity Matroids
Hiro Ito; Shin-Ichi Tanigawa; Yuichi Yoshida
AUTOMATA, LANGUAGES, AND PROGRAMMING, ICALP 2012 PT I, SPRINGER-VERLAG BERLIN, 7391巻, 7391号, 掲載ページ 498-509, 出版日 2012年, 査読付, A graph G = (V, E) is called (k, l)-sparse if |F| <= k|V (F)|-l for any F subset of E with F not equal empty set. Here, V (F) denotes the set of vertices incident to F. A graph G = (V, E) is called (k, l)-full if G contains a (k, l)-sparse subgraph with |V | vertices and k|V | - l edges. The family of edge sets of (k, l)-sparse subgraphs forms a family of independent sets of a matroid on E, known as the sparsity matroid of G. In this paper, we give a constant-time algorithm that approximates the rank of the sparsity matroid associated with a degree-bounded undirected graph. This algorithm leads to a constant-time tester for (k, l)-fullness in the bounded-degree model, (i.e., we can decide with high probability whether the input graph satisfies a property or far from it). Depending on the values of k and l, our algorithm can test various properties of graphs such as connectivity, rigidity, and how many spanning trees can be packed in a unified manner.
Based on this result, we also propose a constant-time tester for (k, l)-edge-connected-orientability in the bounded-degree model, where an undirected graph G is called (k, l)-edge-connected-orientable if there exists an orientation G of G with a vertex r is an element of V such that G contains k arc-disjoint dipaths from r to each vertex v is an element of V and l arc-disjoint dipaths from each vertex v is an element of V to r.
A tester is called a one-sided error tester for P if it always accepts a graph satisfying P. We show, for any k >= 2 and (proper) l >= 0, every one-sided error tester for (k, l)-fullness and (k, l)-edge-connected-orientability requires Omega(n) queries.
研究論文（国際会議プロシーディングス）, 英語 - An online algorithm optimally self-tuning to congestion for power management problems
Wolfgang Bein; Naoki Hatta; Nelson Hernandez-Cons; Hiro Ito; Shoji Kasahara; Jun Kawahara
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7164巻, 掲載ページ 35-48, 出版日 2012年, 査読付, We consider the classical power management problem: There is a device which has two states ON and OFF and one has to develop a control algorithm for changing between these states as to minimize (energy) cost when given a sequence of service requests. Although an optimal 2-competitive algorithm exists, that algorithm does not have good performance in many practical situations, especially in case the device is not used frequently. To take the frequency of device usage into account, we construct an algorithm based on the concept of "slackness degree." Then by relaxing the worst case competitive ratio of our online algorithm to 2 + ε, where ε is an arbitrary small constant, we make the algorithm flexible to slackness. The algorithm thus automatically tunes itself to slackness degree and gives better performance than the optimal 2-competitive algorithm for real world inputs. In addition to worst case competitive ratio analysis, a queueing model analysis is given and computer simulations are reported, confirming that the performance of the algorithm is high. © 2012 Springer-Verlag.
研究論文（国際会議プロシーディングス）, 英語 - IMPROVED CONSTANT-TIME APPROXIMATION ALGORITHMS FOR MAXIMUM MATCHINGS AND OTHER OPTIMIZATION PROBLEMS
Yuichi Yoshida; Masaki Yamamoto; Hiro Ito
SIAM JOURNAL ON COMPUTING, SIAM PUBLICATIONS, 41巻, 4号, 掲載ページ 1074-1093, 出版日 2012年, 査読付, We study constant-time approximation algorithms for bounded-degree graphs, which run in time independent of the number of vertices n. We present an algorithm that decides whether a vertex is contained in a some fixed maximal independent set with expected query complexity O(d(2)), where d is the degree bound. Using this algorithm, we show constant-time approximation algorithms with certain multiplicative error and additive error is an element of n for many other problems, e.g., the maximum matching problem, the minimum vertex cover problem, and the minimum set cover problem, that run exponentially faster than existing algorithms with respect to d and 1/is an element of. Our approximation algorithm for the maximum matching problem can be transformed to a two-sided error tester for the property of having a perfect matching. On the contrary, we show that every one-sided error tester for the property requires at least Omega(n) queries.
研究論文（学術雑誌）, 英語 - Complexity of the stamp folding problem
UMESATO Takuya; SAITOH Toshiki; UEHARA Ryuhei; ITO Hiro; OKAMOTO Yoshio
Theoretical Computer Science, 497巻, 29号, 掲載ページ 13-19, 出版日 2012年, 査読付
研究論文（学術雑誌）, 英語 - Constant-Time Approximation Algorithms for the Optimum Branching Problem on Sparse Graphs
Mitsuru Kusumoto; Yuichi Yoshida; Hiro Ito
2012 THIRD INTERNATIONAL CONFERENCE ON NETWORKING AND COMPUTING (ICNC 2012), IEEE, 掲載ページ 407-413, 出版日 2012年, 査読付, We propose constant-time algorithms for approximating the weight of the maximum weight branching in the general graph model. A directed graph is called a branching if it is acyclic and each vertex has at most one incoming edge. An edge-weighted digraph G, in which weights are given in real values in [0, 1], of average degree d is given as an oracle access, and we are allowed to ask degrees and incoming edges for every vertex through the oracle. Then, with high probability, our algorithm estimates the weight of the maximum weight branching in G with an absolute error of at most epsilon n with query complexity O(d/epsilon(3)), where n is the number of vertices. We also show a lower bound of Omega(d/epsilon(3)). Additionally, our algorithm can be modified to run with query complexity O(1/epsilon(4)) for unweighted digraphs, i.e., it runs in time independent of the input size even for digraphs with Omega(n(2)) edges. In contrast, we show that it requires Omega(n) queries to approximate the weight of the minimum (or maximum) spanning arborescence in a weighted digraph.
研究論文（国際会議プロシーディングス）, 英語 - Helly numbers of polyominoes
Jean CARDINAL; ITO Hiro; Matias KORMAN; Stefan LANGERMAN
The 23rd Canadian Conference on Computational Geometry (CCCG'11), 掲載ページ 443--448, 出版日 2011年08月, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Testing Algorithms for (k, l)-Sparsity and (k, l)-Edge-Connected Orientability
Hiro Ito; Shin-ichi Tanigawa; Yuichi Yoshida
Proc. 7th Hungarian-Japanese Symposium on Discrete Math, 掲載ページ 447-456, 出版日 2011年05月
研究論文（研究会，シンポジウム資料等）, 英語 - Arrangements of n Points whose Incident-Line-Numbers are at most n/2
Jin Akiyama; Hiro Ito; Midori Kobayashi; Gisaku Nakamura
GRAPHS AND COMBINATORICS, SPRINGER TOKYO, 27巻, 3号, 掲載ページ 321-326, 出版日 2011年05月, 査読付, We consider a set X of n noncollinear points in the Euclidean plane, and the set of lines spanned by X, where n is an integer with n a parts per thousand yen 3. Let t(X) be the maximum number of lines incident with a point of X. We consider the problem of finding a set X of n noncollinear points in the Euclidean plane with t(X) <= [n/2], for every integer n a parts per thousand yen 8. In this paper, we settle the problem for every integer n except n = 12k + 11 (k a parts per thousand yen 4). The latter case remains open.
研究論文（学術雑誌）, 英語 - Cannibal animal games: a new variant of tic-tac-toe
Jean CARDINAL; Sebastien COLETTE; ITO Hiro; Matias KORMAN; Stefan LANGERMAN; SAKIDANI Hikaru; Perouz TASLAKIAN
The 27th European Workshop on Computational Geometry (EuroCG 2011), 掲載ページ 131--134, 出版日 2011年03月, 査読付
研究論文（国際会議プロシーディングス）, 英語 - PSPACE-completeness of the Weighted Poset Game
Hiro Ito; Satoshi Takata
OPERATIONS RESEARCH AND ITS APPLICATIONS: IN ENGINEERING, TECHNOLOGY AND MANAGEMENT, WORLD PUBLISHING CORPORATION, 14巻, 掲載ページ 89-93, 出版日 2011年, 査読付, Poset game, which includes some famous games. e.g., Nim and Chomp as sub-games, is an important two-player impartial combinatorial game. The rule of the game is as follows: For a given poset (partial ordered set), each player intern chooses an element and the selected element and it's descendants (elements succeeding it) are all removed from the poset. A player who choose the last element is the winner. On the complexity of poset game, although it is clearly in PSPACE, it have not known whether it is in P or NP-hard. Recently a weighted poset game, which is a generalization of poset game, have been presented and it was found that some sub-games of it can be solved in polynomial-time. The complexity of this game is also open. This paper shows that weighted poset game is PSPACE-complete even if the weights are restricted in {1, -1}, the dag, which represents the poset, is bipartite, and the length of each path in the dag is at most two.
研究論文（国際会議プロシーディングス）, 英語 - Making Polygons by Simple Folds and One Straight Cut
Erik D. Demaine; Martin L. Demaine; Andrea Hawksley; Hiro Ito; Po-Ru Loh; Shelly Manber; Omani Stephens
COMPUTATIONAL GEOMETRY, GRAPHS AND APPLICATIONS, SPRINGER-VERLAG BERLIN, 7033巻, 掲載ページ 27-+, 出版日 2011年, 査読付, We give an efficient algorithmic characterization of simple polygons whose edges can be aligned onto a common line, with nothing else on that line, by a sequence of all-layers simple folds. In particular, such alignments enable the cutting out of the polygon and its complement with one complete straight cut. We also show that these makeable polygons include all convex polygons possessing a line of symmetry.
研究論文（国際会議プロシーディングス）, 英語 - Complexity of the Stamp Folding Problem
Takuya Umesato; Toshiki Saitoh; Ryuhei Uehara; Hiro Ito
COMBINATORIAL OPTIMIZATION AND APPLICATIONS, SPRINGER-VERLAG BERLIN, 6831巻, 掲載ページ 311-321, 出版日 2011年, 査読付, For a given mountain-valley pattern of equidistant creases on a lone paper strip, there are many folded states consistent with the pattern. Among these folded states, we like to fold a paper so that the number of the paper layers between each pair of hinged paper segments. which is called the crease width at the crease point, is minimized. This problem is called the stamp folding problem and there are two variants of this problem; minimization of the maximum crease width, and minimization of the total crease width. This optimization problem is recently introduced and investigated from the viewpoint of the counting problem. However, its computational complexity is not known. In this paper, we first show that the minimization problem of the maximum crease width is strongly NP-complete. Hence we cannot solve the problem in polynomial time unless P=NP. We next propose an algorithm that solves the minimization problem. The algorithm itself is a straightforward one, but its analysis is not trivial. We show that this algorithm runs in O(n(2)((n+k)(k))) time where n is the number of creases and k is the total crease width. That is, the algorithm runs in O(n(k+2)) time for a constant k. Hence we can solve the problem efficiently for a small constant k.
研究論文（国際会議プロシーディングス）, 英語 - Query-Number Preserving Reductions and Linear Lower Bounds for Testing
Yuichi Yoshida; Hiro Ito
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, E93D巻, 2号, 掲載ページ 233-240, 出版日 2010年02月, 査読付, In this paper, we study lower bounds on the query complexity of testing algorithms for various problems. Given an oracle that returns information of an input object, a testing algorithm distinguishes the case that the object has a given property P from the case that it has a large distance to having P with probability at least 2. The query complexity of an algorithm is measured by the number of accesses to the oracle. We introduce two reductions that preserve the query complexity. One is derived from the gap-preserving local reduction and the other is from the L-reduction. By using the former reduction, we show linear lower bounds on the query complexity for testing basic NP-complete properties, i.e., 3-edge-colorability, directed Hamiltonian path/cycle, undirected Hamiltonian path/cycle, 3-dimensional matching and NP-complete generalized satisfiability problems. Also, using the second reduction, we show a linear lower bound on the query complexity of approximating the size of the maximum 3-dimensional matching.
研究論文（学術雑誌）, 英語 - TESTING k-EDGE-CONNECTIVITY OF DIGRAPHS
Yuichi Yoshida; Hiro Ito
JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY, SPRINGER, 23巻, 1号, 掲載ページ 91-101, 出版日 2010年02月, 査読付, This paper presents an algorithm that tests whether a given degree-bounded digraph is k-edge-connected or e-far from k-edge-connectivity. This is the first testing algorithm for k-edge-connectivity of digraphs whose running time is independent of the number of vertices and edges. A digraph of n vertices with degree bound d is e-far from k-edge-connectivity if at least epsilon dn edges have to be added or deleted to make the digraph k-edge-connected, preserving the degree bound. Given a constant error parameter e and a degree bound d, our algorithm always accepts all k-edge-connected digraphs and rejects all digraphs that is e-far from k-edge-connectivity with probability at least 2/3. It runs in O(d (c/epsilon d)(k) log 1/epsilon dO)(c > 1 is a constant) time when input diagraphs are restricted to be (k-1)-edge connected and runs in O(d(ck/epsilon d)(k) log k/epsilon dO) (c > 1 is a constant) time for general digraphs.
研究論文（学術雑誌）, 英語 - Tractability and Intractability of Problems on Unit Disk Graphs Parameterized by Domain Area
Hiro Ito; Masakazu Kadoshita
OPERATIONS RESEARCH AND ITS APPLICATIONS, WORLD PUBLISHING CORPORATION, 12巻, 掲載ページ 120-127, 出版日 2010年, 査読付, This paper treats unit disk graphs whose vertices are located in a square-shaped region with fixed area alpha, and considers parametrized problems on this model. It shows that "fixed area" is not a trivial restriction by proving that the maximum independent set problem and the minimum dominating set problem are both W[1]-complete for unit disk graphs parameterized by area. On the other hand, it shows an algorithm that solves the Hamiltonian circuit problem in O(m + p(2)c(P)) time, where m is the number of edges, p = 2 alpha + o(alpha), and c is a constant number, i.e., this problem is FPT for the parameter alpha. It also shows an algorithm that solves the k-coloring problem in O(k(kP)) time, i.e., this problem is also FPT for the pair of parameters k and alpha.
研究論文（国際会議プロシーディングス）, 英語 - Testing Outerplanarity of Bounded Degree Graphs
Yuichi Yoshida; Hiro Ito
APPROXIMATION, RANDOMIZATION, AND COMBINATORIAL OPTIMIZATION: ALGORITHMS AND TECHNIQUES, SPRINGER-VERLAG BERLIN, 6302巻, 掲載ページ 642-655, 出版日 2010年, 査読付, We present an efficient algorithm for testing outerplanarity of graphs in the bounded degree model. In this model, given a graph G with n vertices and degree bound d. we should distinguish with high probability the case that G is outerplanar from the case that modifying at least an c-fraction of the edge set of G is necessary to make G outerplanar.
Our algorithm runs in (O) over tilde (1/epsilon(13)d(6) + d/(epsilon)2) time, which is independent of the size of graphs. This is the first algorithm for a non-trivial minor-closed property whose time complexity is polynomial in 1/epsilon and d. To achieve the time complexity, we exploit the tree-like structure inherent to an outerplanar graph using the microtree/macrotree decomposition of a tree.
As a corollary, we also show an algorithm that tests whether a given graph is a cactus with time complexity (O) over tilde (1/epsilon(13)d(6) + d/epsilon(2)).
研究論文（国際会議プロシーディングス）, 英語 - Enumeration of Isolated Cliques and Pseudo-Cliques
Hiro Ito; Kazuo Iwama
ACM TRANSACTIONS ON ALGORITHMS, ASSOC COMPUTING MACHINERY, 5巻, 4号, 掲載ページ Article 40, 出版日 2009年10月, 査読付, In this article, we consider isolated cliques and isolated dense subgraphs. For a given graph G, a vertex subset S of size k (and also its induced subgraph G(S)) is said to be c-isolated if G(S) is connected to its outside via less than ck edges. The number c is sometimes called the isolation factor. The subgraph appears more isolated if the isolation factor is smaller. The main result in this work shows that for a fixed constant c, we can enumerate all c-isolated maximal cliques (including a maximum one, if any) in linear time.
In more detail, we show that, for a given graph G of n vertices and m edges, and a positive real number c, all c-isolated maximal cliques can be enumerated in time O(c(4)2(2c)m). From this, we can see that: (1) if c is a constant, all c-isolated maximal cliques can be enumerated in linear time, and (2) if c = O( log n), all c-isolated maximal cliques can be enumerated in polynomial time. Moreover, we show that these bounds are tight. That is, if f(n) is an increasing function not bounded by any constant, then there is a graph of n vertices and m edges for which the number of f(n)-isolated maximal cliques is superlinear in n + m. Furthermore, if f (n) = omega(log n), there is a graph of n vertices and m edges for which the number of f(n)-isolated maximal cliques is superpolynomial in n + m.
We next introduce the idea of pseudo-cliques. A pseudo-clique having an average degree a and a minimum degree beta, denoted by PC(alpha, beta), is a set V' subset of V such that the subgraph induced by V' has an average degree of at least alpha and a minimum degree of at least beta. This article investigates these, and obtains some cases that can be solved in polynomial time and some other cases that have a superpolynomial number of solutions. Especially, we show the following results, where k is the number of vertices of the isolated pseudo-cliques: (1) For any epsilon > 0 there is a graph of n vertices for which the number of 1-isolated PC(k - (logk)(1+epsilon), k/(log k)(1+epsilon)) is superpolynomial, and (2) there is a polynomial-time algorithm which enumerates all c-isolated PC(k - log k, k/log k), for any constant c.
研究論文（学術雑誌）, 英語 - Maximum-cover source location problems with objective edge-connectivity three
Kenya Sugihara; Hiro Ito
MATHEMATICAL METHODS OF OPERATIONS RESEARCH, SPRINGER HEIDELBERG, 70巻, 1号, 掲載ページ 183-193, 出版日 2009年08月, 査読付, Given a graph G = (V, E), a set of vertices S subset of V covers a vertex v is an element of V if the edge-connectivity between S and v is at least a given number k. Vertices in S are called sources. The maximum-cover source location problem, which is a variation of the source location problem, is to find a source set S with a given size at most p, maximizing the sum of the weight of vertices covered by S. In this paper, we show a polynomial-time algorithm for this problem in the case of k = 3 for a given undirected graph with a vertex weight function and an edge capacity function. Moreover, we show that this problem is NP-hard even if vertex weights and edge capacities are both uniform for general k.
研究論文（学術雑誌）, 英語 - An Improved Constant-Time Approximation Algorithm for Maximum Matchings
Yuichi Yoshida; Masaki Yamamoto; Hiro Ito
STOC'09: PROCEEDINGS OF THE 2009 ACM SYMPOSIUM ON THEORY OF COMPUTING, ASSOC COMPUTING MACHINERY, 掲載ページ 225-234, 出版日 2009年, 査読付, This paper studies constant-time approximation algorithms for problems on degree-bounded graphs. Let n and d be the number of vertices and the, degree bound, respectively.
This paper presents an algorithm that decides whether a, vertex is contained in a some fixed maximal independent set with expected query complexity O(d(2)). Using this algorithm. it also shows that there are approximation algorithms with additive error epsilon n. for many other problems, e.g., the maximum matching problem, the minimum vertex cover problem. and file minimum set cover problem, that run exponentially than existing algorithms with respect to d and 1/c.
Its approximation algorithm for the maximum matching can be transformed to a testing algorithm for the property of having a perfect matching with two-sided error. Oil the contrary, it also shows that every one-sided error tester for the property requires at, least Omega(n) queries.
研究論文（国際会議プロシーディングス）, 英語 - Inferring pedigree graphs from genetic distances
Takeyuki Tamura; Hiro Ito
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, E91D巻, 2号, 掲載ページ 162-169, 出版日 2008年02月, 査読付, In this paper, we study a problem of inferring blood relationships which satisfy a given matrix of genetic distances between all pairs of n nodes. Blood relationships are represented by our proposed graph class, which is called a pedigree graph. A pedigree graph is a directed acyclic graph in which the maximum indegree is at most two. We show that the number of pedigree graphs which satisfy the condition of given genetic distances may be exponential, but they can be represented by one directed acyclic graph with n nodes. Moreover, an O(n(3)) time algorithm which solves the problem is also given. Although phylogenetic trees and phylogenetic networks are similar data structures to pedigree graphs, it seems that inferring methods for phylogenetic trees and networks cannot be applied to infer pedigree graphs since nodes of phylogenetic trees and networks represent species whereas nodes of pedigree graphs represent individuals. We also show an O(n(2)) time algorithm which detects a contradiction between a given pedigree graph and distance matrix of genetic distances.
研究論文（学術雑誌）, 英語 - Enumeration of Tsume-Shogi diagrams by the reverse method
Takashi Horiyama; Hiro Ito; Kazuo Iwama; Jun Kawahara
INTERNATIONAL CONFERENCE ON INFORMATICS EDUCATION AND RESEARCH FOR KNOWLEDGE-CIRCULATING SOCIETY, PROCEEDINGS, IEEE COMPUTER SOC, 掲載ページ 193-+, 出版日 2008年, 査読付, With the advances of modern computer technologies and elaborated algorithm design methodologies, it becomes important to enumerate all feasible solutions for given constraints. In this paper, we propose algorithms for enumerating Tsume-Shogi diagrams (i.e., Shogi. mating problems) by the reverse method. Conventional algorithms always take the principle 'generate candidate diagrams and sieve them by Tsume-Shogi solvers,' which tends to require lengthy execution time. In our approach, the reverse method enables us to enumerate all diagrams without using Tsume-Shogi solvers. We can sieve the candidates easily and quickly, since the), are generated in the ascending order according to the number of necessary moves for mating the defender's king. We have implemented the proposed algorithms, and enumerated all diagrams with several restrictions (e.g., those with only four knights). From this result, we prove many results for knight diagrams, e.g., i) the maximum number of moves is 11, ii) it is 13 for additional mate free, iii) it is 7 if at least one piece is in hand of the attacker, and iv) the maximum pieces in hand of the attacker is two.
研究論文（国際会議プロシーディングス）, 英語 - Multi-commodity source location problems and price of greed
Hiro Ito; Mike Paterson; Kenya Sugihara
WALCOM: ALGORITHMS AND COMPUTATION, PROCEEDINGS, SPRINGER-VERLAG BERLIN, 4921巻, 掲載ページ 169-+, 出版日 2008年, 査読付, Given a graph G = (V, E), we say that a vertex subset S subset of V covers a vertex v epsilon V if the edge-connectivity between S and v is at least a given integer k, and also say that S covers an edge vw epsilon E if v and w are covered. We propose the multi-commodity source location problem, which is such that given a vertex- and edge-weighted graph G, r players each select p vertices, and obtain a profit that is the total weight of covered vertices and edges. However, vertices selected by one player cannot be selected by the other players. The goal is to maximize the total profits of all players. We show that the price of greed, which indicates the ratio of the total profit of cooperating players to that of selfish players, is tightly bounded by min {r, p}. Also when k = 2, we obtain tight bounds for vertex-unweighted trees.
研究論文（国際会議プロシーディングス）, 英語 - Property testing on k-vertex-connectivity of graphs
Yuichi Yoshida; Hiro Ito
AUTOMATA, LANGUAGES AND PROGRAMMING, PT 1, PROCEEDINGS, SPRINGER-VERLAG BERLIN, 5125巻, 掲載ページ 539-550, 出版日 2008年, 査読付, We present an algorithm for testing the k-vertex-connectivity of graphs with given maximum degree. The time complexity of the algorithm is independent of the number of vertices and edges of graphs. A graph G with n vertices and maximum degree at most d is called epsilon-far from k-vertex-connectivity when at least epsilon dn/2 edges must be added to or removed from G to obtain a k-vertex-connected graph with maximum degree at most d. The algorithm always accepts every graph that is k-vertex-connected and rejects every graph that is epsilon-far from k-vertex-connectivity with a probability of at least 2/3. The algorithm runs in O (d (c/epsilon d)(k) log 1/epsilon d) time (c > 1 is a constant) for given (k - 1)-vertex-connected graphs, and O (d (ck/epsilon d)(k) log k/epsilon d) time (c > 1. is a constant) for given general graphs. It is the first constant-time k-vertex-connectivity testing algorithm for general k > 4.
研究論文（国際会議プロシーディングス）, 英語 - Transforming Graphs with the Same Degree Sequence
Sergey Bereg; Hiro Ito
COMPUTATIONAL GEOMETRY AND GRAPH THEORY, SPRINGER-VERLAG BERLIN, 4535巻, 掲載ページ 25-+, 出版日 2008年, 査読付, Let G and H be two graphs with the same vertex set; V. It is well known that a graph G can be transformed into a graph H by a sequence of 2-switches if and only if every vertex of V has the same degree in both G and H. We study the problem of finding the minimum number of 2-switches for transforming G into H.
研究論文（国際会議プロシーディングス）, 英語 - Multi-commodity source location problems and price of greed
Hiro Ito; Mike Paterson; Kenya Sugihara
WALCOM: ALGORITHMS AND COMPUTATION, PROCEEDINGS, SPRINGER-VERLAG BERLIN, 4921巻, 1号, 掲載ページ 169-+, 出版日 2008年, 査読付, Given a graph G = (V, E), we say that a vertex subset S subset of V covers a vertex v epsilon V if the edge-connectivity between S and v is at least a given integer k, and also say that S covers an edge vw epsilon E if v and w are covered. We propose the multi-commodity source location problem, which is such that given a vertex- and edge-weighted graph G, r players each select p vertices, and obtain a profit that is the total weight of covered vertices and edges. However, vertices selected by one player cannot be selected by the other players. The goal is to maximize the total profits of all players. We show that the price of greed, which indicates the ratio of the total profit of cooperating players to that of selfish players, is tightly bounded by min {r, p}. Also when k = 2, we obtain tight bounds for vertex-unweighted trees.
研究論文（国際会議プロシーディングス）, 英語 - Snaky is a winner with one handicap
ITO Hiro; MIYAGAWA Hiromitsu
8th Hellenic European Conference on Computer Mathematics and its Applications (HERCMA 2007), 掲載ページ 25--26, 出版日 2007年09月, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Winning ways of weighted poset games
Hiro Ito; Gisaku Nakamura; Satoshi Takata
GRAPHS AND COMBINATORICS, SPRINGER TOKYO, 23巻, 掲載ページ 291-306, 出版日 2007年, 査読付, In this paper, we introduce the weighted poset game, which is defined as an extension of the poset (partially ordered set) game by adding a weight on every element of the poset. Each player has their own non-negative number of lives, and loses as many lives as the sum of the element weights they took. The player whose lives become negative first is the loser. We consider winning ways of this problem. First, for the problem with {0, 1}-weights, we find that (1) if the number of lives are different, then the player who has the large number of lives is the winner, (2) if the number of lives are the same and all maximal elements have positive weights, then the second player is a winner, and (3) otherwise, the game is reduced to an (unweighted) poset game. Next, for general weights, we consider the case where the partial order is a total order, and derive a polynomial-time algorithm for calculating who is the winner and the winning way for the winner.
研究論文（学術雑誌）, 英語 - Semi-distance codes and Steiner systems
Hiro Ito; Midori Kobayashi; Gisaku Nakamura
GRAPHS AND COMBINATORICS, SPRINGER TOKYO, 23巻, 掲載ページ 283-290, 出版日 2007年, 査読付, Let C be a d-semi-distance code of length n and N the cardinality of C. In this paper we obtain an upper bound on
[GRAPHICS]
where k(0) = [ (n + d - 1)/2]. When a code C attains the upper bound and n + d - 1 is even, C corresponds to a Steiner system S(k(0) - d+ 1, k(0), n) in anatural way. Let S be a Steiner system S(t, k, n) with k+t - 1 <= n <= k + t + 1 (1 <= t <= k <= n). Then S corresponds to an optimal (k - t + 1)-semi-distance code of length n in a natural way.
研究論文（学術雑誌）, 英語 - Impossibility of transformation of vertex labeled simple graphs preserving the cut-size order
Hiro Ito
Discrete Geometry, Combinatorics and Graph Theory, SPRINGER-VERLAG BERLIN, 4381巻, 掲載ページ 59-69, 出版日 2007年, 査読付, Three partial orders, cut-size order, length order, and operation order, defined between labeled graphs with the same number of vertices are known to be equivalent. From the equivalence, G precedes G' in the order means that there is a sequence of cross-operations transforming G into G'. However, even if both graphs are simple, non-simple graphs may appear on the way of the transformation. If both graphs have the same number of edges, we conjecture that there is a sequence in which only simple graphs appear. But for graphs having different number of edges, there is a counter example. That is, there is a pair of simple graphs G and G' such that G precedes G' in the order and G can not be transformed into G' by using only simple graphs. Thus we must introduce other operations than cross-operation for transforming them by using only simple graphs. Then we naturally reach to a question: is there a sufficient set of operations for this purpose? For this problem, this paper shows a negative result that there is no such finite set of operations.
研究論文（国際会議プロシーディングス）, 英語 - Infinite series of generalized Gosper space filling curves
Jin Akiyama; Hiroshi Fukuda; Hiro Ito; Gisaku Nakamura
DISCRETE GEOMETRY, COMBINATORICS AND GRAPH THEORY, SPRINGER-VERLAG BERLIN, 4381巻, 掲載ページ 1-+, 出版日 2007年, 査読付, We report on computer search for generalized Cosper curve for 37 < N < 61, where N is the degree of the generalized Gosper curve. From the results of the computer search and some geometrical insight, we conjecture that the degree N satisfies N = 6n+ 1. We investigate the existence of infinite series of generalized Gosper curves. We show how to generate these series and introduce two new methods, the `decomposition method' and the 'modified layer method'.
研究論文（国際会議プロシーディングス）, 英語 - Maximum-Cover Source-Location Problem with Objective Edge-Connectivity Three
Kenya Sugihara; Hiro Ito
Electronic Notes in Discrete Mathematics, 25巻, 掲載ページ 165-171, 出版日 2006年08月01日, 査読付
研究論文（学術雑誌）, 英語 - Efficient methods for determining DNA probe orders
Ito Hiro; Iwama Kazuo; Takeyuki Tamura
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, E89A巻, 5号, 掲載ページ 1292-1298, 出版日 2006年05月, 査読付 - Maximum-cover source-location problems
Kenya Sugihara; Hiro Ito
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, E89A巻, 5号, 掲載ページ 1370-1377, 出版日 2006年05月, 査読付, Given a graph G = (V, E), a set of vertices S subset of V covers v is an element of V if the edge connectivity between S and v is at least a given number k. Vertices in S are called sources. The source location problem is a problem of finding a minimum-size source set covering all vertices of a given graph. This paper presents a new variation of the problem, called maximum-cover source-location problem, which finds a source set S with a given size p, maximizing the sum of the weight of vertices covered by S. It presents an O(np + m + n log n)-time algorithm for k = 2, where n = \V\ and m = \E\. Especially it runs linear time if G is connected. This algorithm uses a subroutine for finding a subtree with the maximum weight among p-leaf trees of a given vertex-weighted tree. For the problem we give a greedy-based linear-time algorithm, which is an extension of the linear-time algorithm for finding a longest path of a given tree presented by E. W. Dijkstra around 1960. Moreover, we show some polynomial solvable cases, e.g., a given graph is a tree or (k - 1)-edge-connected, and NP-hard cases, e.g., a vertex-cost function is given or G is a digraph.
研究論文（学術雑誌）, 英語 - ハラリイの一般化三並べ
伊藤大雄
信学論, J89-A巻, 6号, 掲載ページ 458--469, 出版日 2006年, 査読付
研究論文（学術雑誌）, 日本語 - Efficient methods of determining DNA probe sequences
ITO Hiro; IWAMA Kazuo; TAMURA Takeyuki
IEICE Transactions, E89-A巻, 5号, 掲載ページ 1292--1298, 出版日 2006年, 査読付
研究論文（学術雑誌）, 英語 - Two equivalent measures on weighted hypergraphs
ITO Hiro; NAGAMOCHI Hiroshi
Discrete Applied Mathematics, 154巻, 掲載ページ 2330--2334, 出版日 2006年, 査読付
研究論文（学術雑誌）, 英語 - Single backup table schemes for shortest-path routing
H Ito; K Iwama; Y Okabe; T Yoshihiro
THEORETICAL COMPUTER SCIENCE, ELSEVIER SCIENCE BV, 333巻, 3号, 掲載ページ 347-353, 出版日 2005年03月, 査読付, We introduce a new recovery scheme that needs only one extra backup routing table for networks employing shortest-path routing. By precomputing this backup table, the network recovers from any single link failure immediately after the failure occurs. To compute the backup routing table for this scheme, we use an almost linear time algorithm to solve the {r, v}-problem, which is a variation of the best swap problem presented by Nardelli et al. We further show that the same solution can be computed in exactly linear time if the underlying graph is unweighted. (c) 2004 Elsevier B.V. All rights reserved.
研究論文（学術雑誌）, 英語 - Linear-time enumeration of isolated cliques
H Ito; K Iwama; T Osumi
ALGORITHMS - ESA 2005, SPRINGER-VERLAG BERLIN, 3669巻, 掲載ページ 119-130, 出版日 2005年, 査読付, For a given graph G of n vertices and m edges, a clique S of size k is said to be c-isolated if there are at most ck outgoing edges from S. It is shown that this parameter c is an interesting measure which governs the complexity of finding cliques. In particular, if c is a constant, then we can enumerate all c-isolated maximal cliques in linear time, and if c = O(log n), then we can enumerate all c-isolated maximal cliques in polynomial time. Note that there is a graph which has a superlinear number of c-isolated cliques if c is not a constant, and there is a graph which has a superpolynomial number of c-isolated cliques if c = omega(log n). In this sense our algorithm is optimal for the linear-time and polynomial-time enumeration of c-isolated cliques.
研究論文（学術雑誌）, 英語 - Three equivalent partial orders on graphs with real edge-weights drawn on a convex polygon
H Ito
DISCRETE AND COMPUTATIONAL GEOMETRY, SPRINGER-VERLAG BERLIN, 3742巻, 掲載ページ 123-130, 出版日 2005年, 査読付, Three partial orders, cut-size order, length order, and operation order, defined between labeled multigraphs with the same order are known to be equivalent. This paper extends the result on edge-capacitated graphs, where the capacities are real numbers, and it presents a proof of the equivalence of the three relations. From this proof, it is also shown that we can determine whether or not a given graph precedes another given graph in polynomial time.
研究論文（学術雑誌）, 英語 - NA-edge-connectivity augmentation problems by adding edges
HH Miwa; H Ito
JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF JAPAN, ELSEVIER SCI LTD, 47巻, 4号, 掲載ページ 224-243, 出版日 2004年12月, 査読付, The network reliability in multi-server environment is measured by the connectivity between a vertex and a vertex subset (NA-connectivity). The problem of augmenting a graph by adding the smallest number of new edges to meet NA-edge (vertex)-connectivity requirement is an important optimization problem that contributes to the network design problem to increase the reliability of a current network by adding the smallest number of links. this problem is a generalization of the well-known connectivity augmentation problems.
In this paper, we focus on the NA-edge-connectivity augmentation problem. First, we prove the NP-completeness of the problem which determines whether we can augment a graph to a 1-NA-edge-connected graph by adding a given number or less new edges. Next, we prove that the problem of augmenting a 1-NA-edge-connected graph or a 0-NA-edge-connected graph to be 2-NA-edge-connected graph by adding the smallest number of edges can be solved in polynomial time.
研究論文（学術雑誌）, 英語 - Subdivision of the hierarchy of H-colorable graph classes by circulant graphs
UEJIMA Akihiro; ITO Hiro
Proceedings of CTW2004 Workshop on Graphs and Combinatorial Optimization, 掲載ページ 232--236, 出版日 2004年05月, 査読付
研究論文（国際会議プロシーディングス）, 英語 - C_7-coloring problem
A Uejima; H Ito; T Tsukiji
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, E87A巻, 5号, 掲載ページ 1243-1250, 出版日 2004年05月, 査読付, H-coloring problem is a coloring problem with restrictions such that some pairs of colors cannot be used for adjacent vertices, where H is a graph representing the restrictions of colors. We deal with the case that H is the complement graph (C2p+1) over bar of a cycle of odd order 2p + 1. This paper presents the following results: (1) chordal graphs and internally maximal planar graphs are (C2p+1) over bar -colorable if and only if they are p-colorable (p greater than or equal to 2), (2) C-7-coloring problem on planar graphs is NP-complete, and (3) there exists a class that includes infinitely many (C-7) over bar -colorable but non-3-colorable planar graphs.
研究論文（学術雑誌）, 英語 - Imperfectness of data for STS-based physical mapping
H Ito; K Iwama; T Tamura
EXPLORING NEW FRONTIERS OF THEORETICAL INFORMATICS, SPRINGER, 155巻, 掲載ページ 279-292, 出版日 2004年, 査読付, In the STS-based mapping, we are requested to obtain the correct order of probes in a DNA sequence from a given set of fragments or equivalently a hybridization matrix A. It is well-known that the problem is formulated as the combinatorial problem of obtaining a permutation of A's columns so that the resulting matrix has the consecutive-one property. If the data (the hybridization matrix) is error free and includes enough information, then the above column order determines the correct order of the probes uniquely. Unfortunately this is no longer true if the data include errors, which has been one of the popular research targets in computational biology. Even if there is no error, ambiguities in the probe order may still remain. This in fact happens by the lack of some information of the data, but almost no further investigation was made previously. In this paper, we define a measure of such imperfectness of the data as a minimum amount of additional fragments which are needed to fix the probe order uniquely. Several polynomial-time algorithms to compute such additional fragments of minimum cost are presented.
研究論文（国際会議プロシーディングス）, 英語 - Avoiding routing loops on the Internet
H Ito; K Iwama; Y Okabe; T Yoshihiro
THEORY OF COMPUTING SYSTEMS, SPRINGER-VERLAG, 36巻, 6号, 掲載ページ 597-609, 出版日 2003年11月, 査読付, Suppose that some particular link in the Internet is currently congested. A natural solution is to try to make packets bypass that link. This can be done by increasing the cost of that link intentionally, say from a(1) to a(2), since the Internet uses shortest-path routing. Unfortunately, however, this often causes temporary loops for packet traveling, called routing loops. In this paper we show that routing loops can be avoided by increasing the cost of the link not directly from a(1) to a(2) but through an intermediate value, a(3), i.e., from a(1) to a(3) and then to a(2). We may need several intermediate values. We show that in this case the greedy strategy, namely, raising the cost as much as possible in each step, is optimal.
研究論文（学術雑誌）, 英語 - Source location problem with flow requirements in directed networks
H Ito; K Makino; K Arata; S Honami; Y Itatsu; S Fujishige
OPTIMIZATION METHODS & SOFTWARE, TAYLOR & FRANCIS LTD, 18巻, 4号, 掲載ページ 427-435, 出版日 2003年08月, 査読付, Given a directed graph G = (V, A) with a capacity function c : A --> R+, two demand functions d(-), d(+) : V --> R+, and a cost function w : V --> R+, we consider the problem of computing a minimum-cost set S subset of or equal to V such that, for each vertex v is an element of V - S, the arc-connectivity from S to v is at least d(-)(v) and the arc-connectivity from v to S is at least d(+)(v). We present a polynomial time algorithm for the problem where d(-) and d(+) are uniformly fixed and w is uniform. Furthermore, we show that the problem is NP-hard, even if either the cost function or the demand function is uniform.
研究論文（学術雑誌）, 英語 - 加群上の畳込み符号による可変レートMPSK符号化変調方式
小西たつ美; 横山光雄; 上原秀幸; 伊藤大雄
信学論, SCRIPTA TECHNICA-JOHN WILEY & SONS, 86巻, 4号, 掲載ページ 20-25, 出版日 2003年, 査読付, This paper proposes variable rate MPSK coded modulation systems using convolutional codes over modules. First, we introduce the definition of the convolutional codes over modules and we illustrate the variable rate coded modulation systems. Next, we show that we can produce the best code for the minimum Hamming distance at any practicable rate, but we cannot get the best code for the minimum free Euclidean distance at any rate in the system. Moreover, we examine the performance in AWGN channels and in Rayleigh fading channels, and we present some properties of our systems. (C) 2002 Wiley Periodicals, Inc.
研究論文（学術雑誌）, 英語 - Sum of edge lengths of a multigraph drawn on a convex polygon
H Ito
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, ELSEVIER SCIENCE BV, 24巻, 1号, 掲載ページ 41-47, 出版日 2003年01月, 査読付, Let x(0), x(1),...., x(n-1) be vertices of a convex n-gon P in the plane, where, x(0)x(1), x(1)x(2),..., x(n-2)x(n-1) and x(n-1)x(0) are edges of P. Let G = (N, E) be a multigraph, such that N = {0,1,..., n-1}. Consider a graph-drawing of G such that each vertex i is an element of N corresponds x(i) and each edge (i, j) is an element of E is drawn by a straight line segment. Denote the sum of the lengths of the edges of G in such a drawing by S-P (G). If S-P (G) less than or equal to Sp (G') for any convex n-gon P, then we write as G less than or equal to(l) G'. This paper shows two necessary and sufficient conditions of G less than or equal to(l) G'. Moreover, these conditions can be calculated in polynomial time for any given G and G'. (C) 2002 Elsevier Science B.V. All rights reserved.
研究論文（学術雑誌）, 英語 - Polynomial time computable backup tables for shortest path routing
ITO Hiro; IWAMA Kazuo; OKABE Yasuo; YOSHIHIRO Takuya
Proceedings of the 10th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2003), Proceedings in Informatics, Carleton Scientific, 17巻, 掲載ページ 163--177, 出版日 2003年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Can a hypergraph cover every convex polygon?
ITO Hiro; NAGAMOCHI Hiroshi
Proceedings of the 3rd Hungarian-Japanese Symposium 2003, 掲載ページ 293--302, 出版日 2003年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Source location problems considering vertex-connectivity and edge-connectivity simultaneously
H Ito; M Ito; Y Itatsu; K Nakai; H Uehara; M Yokoyama
NETWORKS, JOHN WILEY & SONS INC, 40巻, 2号, 掲載ページ 63-70, 出版日 2002年09月, 査読付, Let G = (V, E) be an undirected multigraph, where V and E are a set of vertices and a set of edges, respectively. Let k and I be fixed nonnegative integers. This paper considers location problems of finding a minimum-size vertex-subset S subset of or equal to V such that for each vertex x is an element of V the vertex-connectivity between S and x is greater than or equal to k and the edge-connectivity between S and x is greater than or equal to I. For the problem with edge-connectivity requirements, that is, k = 0, an O(L(\V\, \E\, I)) time algorithm is already known, where L(\V\, \E\, I) is the time to find all h-edge-connected components for h = 1, 2,..., I and O(L(\V\, \E\, I)) = O(\E\ + \V\(2) + \V\min{\E\, I\V\}min{I, \V\}) is known. In this paper, we show that the problem with k greater than or equal to 3 is NP-hard even for I = 0. We then present an O(L(\V\, \E\, I)) time algorithm for 0 less than or equal to k less than or equal to 2 and I less than or equal to 0. Moreover, we prove that the problem parameterized by the size of S is fixed-parameter tractable (FPT) for k = 3 and I greater than or equal to 0. (C) 2002 Wiley Periodicals, Inc.
研究論文（学術雑誌）, 英語 - On H-coloring problems with H expressed by complements of cycles, bipartite graphs, and chordal graphs
A Uejima; H Ito
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, E85A巻, 5号, 掲載ページ 1026-1030, 出版日 2002年05月, 査読付, Coloring problem is a well-known combinatorial optimization problem of graphs. This paper considers H-coloring probdems, which are coloring problems with restrictions such that some pairs of colors can not be used for adjacent vertices. The restriction of adjacent colors call be represented by a graph H, i.e., each vertex represents a color and each edge means that the two colors corresponding to the two end-vertices call be used for adjacent, vertices. Especially. H-coloring problem with a complete graph H of order k is equivalent to the traditional k-coloring problem. This paper presents sufficient conditions such that H-coloring problem can be reduced to an H'-coloring problem; where H' is a subgraph of H. And it shows a hierarchy about classes of H-colorable graphs for any complement graph H of a cycle of order odd n greater than or equal to 5.
研究論文（学術雑誌）, 英語 - マルチホップ無線ネットワークにおける優先領域に基づく中継制御法
北岸弓子; 上原秀幸; 山本亮; 横山光雄; 伊藤大雄
信学論, 一般社団法人電子情報通信学会, J85-B巻, 12号, 掲載ページ 2119--2128-456, 出版日 2002年, 査読付
研究論文（学術雑誌）, 日本語 - 端末のパケット中継機能を用いた安否確認ネットワークの検討
織田将人; 上原秀幸; 横山光雄; 伊藤大雄
信学論, J85-B巻, 12号, 掲載ページ 2037--2044, 出版日 2002年, 査読付
研究論文（学術雑誌）, 日本語 - A Coloring Problem With Restrictions of Adjacent Colors
Uejima Akihiro; Ito Hiro; Uehara Hideyuki; Yokoyama Mitsuo
International Transactions in Operational Research, 9巻, 2号, 掲載ページ 183-194, 出版日 2002年, 査読付, The coloring problem is a well-known problem of graphs. This paper considers a new coloring problem with restrictions such that some pairs of colors cannot be used for adjacent vertices, called coloring problem with restrictions of adjacent colors. The restriction of adjacent colors can be represented by a graph H called a restriction graph, i.e., each vertex represents a color and each edge means that the two colors corresponding to the two end-vertices of the edge cannot be used for adjacent vertices. This paper shows some properties of the new coloring problem. It also presents a necessary and sufficient condition such that a restriction graph H cannot be replaced with a more simple graph, when H is a cactus with no 3-cycle. International Federation of Operational Research Societies 2002.
研究論文（学術雑誌）, 英語 - Channel assignment scheme for integrated voice and data traffic in reservation-type packet radio networks
H Uehara; M Fujihara; M Yokoyama; H Ito
IEICE TRANSACTIONS ON COMMUNICATIONS, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, E85B巻, 1号, 掲載ページ 191-198, 出版日 2002年01月, 査読付, In this paper, we propose, a channel assignment scheme for integrated voice and data traffic in reservation multiple access protocol. In the proposed scheme, a voice packet never contends with a data packet and takes over the slot which is previously assigned to a data packet. Thus, a larger number of voice terminals can be accommodated without degradation of quality and throughput even in the situation that data were integrated. We evaluate the voice packet dropping probability, throughput and packet delay through computer simulation. The results show that the proposed scheme has better performance than the conventional PRMA and DQRUMA systems.
研究論文（学術雑誌）, 英語 - File transfer tree problems
H Ito; H Nagamochi; Y Sugiyama; M Fujita
ALGORITHMS AND COMPUTATION, PROCEEDINGS, SPRINGER-VERLAG BERLIN, 2518巻, 掲載ページ 441-452, 出版日 2002年, 査読付, Given an edge-weighted digraph G with a designated vertex r, and a vertex capacity delta, we consider the problem of finding a shortest path tree T rooted at r such that for each vertex v the number of children of v in T does not exceed the capacity delta(v). The problem has an application in designing a routing for transferring files from the source node to other nodes in an information network. In this paper, we first present an efficient algorithm to the problem. We then introduce extensions of the problem by relaxing the degree constraint or the distance constraint in various ways and show polynomial algorithms or the computational hardness of these problems.
研究論文（学術雑誌）, 英語 - Avoiding routing loops on the Internet
ITO Hiro; IWAMA Kazuo; OKABE Yasuo; YOSHIHIRO Takuya
Proceedings of the 9th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2002), Proceedings in Informatics, Carleton Scientific, 13巻, 掲載ページ 197--210, 出版日 2002年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Comparing hypergraphs by areas of hyperedges drawn on a convex polygon
H Ito; H Nagamochi
DISCRETE AND COMPUTATIONAL GEOMETRY, SPRINGER-VERLAG BERLIN, 2866巻, 掲載ページ 176-181, 出版日 2002年, 査読付, Let H = (N, E, w) be a hypergraph with a node set N = {0, 1,..., n- 1}, a hyperedge set E subset of or equal to 2(N), and real edge-weights w(e) for e E E. Given a convex n-gon P in the plane with vertices x(0), x(1),...., x(n-1) which are arranged in this order clockwisely, we let each node i is an element of N correspond to the vertex x(i) and define the area A(P)(H) of H on P by the sum of weighted areas of convex hulls for all hyperedges in H. For 0 less than or equal to i < j < k less than or equal to n-1, a convex three-cut C(i, j, k) of N is {j,..., k - 1}, {k,..., n - 1, 0,..., i - 1 } } and its size c(H)(i, j, k) in H is defined as the sum of weights of edges e E E such that a contains at least one node from each of {i,...,j - 1}, {j,..., k - 1} and {k,..., n - 1,0,...., i - 1}. We show that for two hypergraphs H and H' on N, the following two conditions are equivalent.
A(P)(H) less than or equal to A(P)(H') for all convex n-gons P.
c(H) (i, j, k) less than or equal to c(H')(i, j, k) for all convex three-cuts C(i, j, k).
研究論文（学術雑誌）, 英語 - Minimum cost source location problem with vertex-connectivity requirements in digraphs
H Nagamochi; T Ishii; H Ito
INFORMATION PROCESSING LETTERS, ELSEVIER SCIENCE BV, 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.
研究論文（学術雑誌）, 英語 - Lengths of tours and permutations on a vertex set of a convex polygon
Hiro, I; U Hideyuki; Y Mitsuo
DISCRETE APPLIED MATHEMATICS, ELSEVIER SCIENCE BV, 115巻, 1-3号, 掲載ページ 63-71, 出版日 2001年11月, 査読付, Let x(0),x(1),...,x(n-1) be vertices of a convex n-gon in the plane (each internal angle may be equal to pi), where, (x(0),x(1)),(x(1),x(2)),...,(x(n-2),x(n-1)), and (x(n-1),x(0)) are edges of the n-gon. Denote the length of the line segment x(i)x(j) by d(ij). Let a be a permutation on {0, 1,...,n - 1}. Define a length of sigma as S(sigma) = Sigma (n-1)(i=0) d(i, sigma (i)). Further, define sigma (p) as sigma (p)(i) = i + p mod n for all i is an element of {0, 1,...,n - 1}. This paper shows that S(sigma (p)) is a strictly concave and strictly increasing function for 1 less than or equal to p less than or equal to [n/2]. It is also shown that sigma ([n/2]) and sigma ([n/2]) are longest permutations and sigma (1) and sigma (n-1) are shortest permutations under some restriction. (C) 2001 Elsevier Science B.V. All rights reserved.
研究論文（学術雑誌）, 英語 - A generalization of 2-dimension Ham Sandwich Theorem
H Ito; H Uehara; M Yokoyama
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, E84A巻, 5号, 掲載ページ 1144-1151, 出版日 2001年05月, 査読付, Let m greater than or equal to 2, n greater than or equal to 2, and q greater than or equal to 2 be positive integers. Let S, and Sb be two disjoint sets of points in the plane such that no three points of S-r boolean OR S-b are collinear, /S-r/ = nq, and /S-b/ = mq. This paper shows that Kaneko and Kano's conjecture is true. i.e., there are q disjoint convex regions of the plain such that each region includes n points of S-r and m points of S-b. This is a generalization of 2-dimension Ham Sandwich Theorem.
研究論文（学術雑誌）, 英語 - Coloring problem with restrictions of adjacent colors expressed by cycles and bipartite graphs
UEJIMA Akihiro; ITO Hiro; UEHARA Hideyuki; YOKOYAMA Mitsuo
Proceedings of the 2nd Japanese-Hungarian Symposium on Discrete Mathematics and Its Application, 掲載ページ 227--236, 出版日 2001年04月, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Source location problem with edge-connectivity requirements in digraphs
ITO Hiro; MAKINO Kazuhisa; ARATA Kouji; ITATSU Yuichiro; FUJISHIGE Satoru
Proceedings of the 2nd Japanese-Hungarian Symposium on Discrete Mathematics and Its Application, 掲載ページ 92--97, 出版日 2001年04月, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Location problems based on node-connectivity, and edge-connectivity between nodes and node-subsets
M Ito; M Ito; Y Itatsu; H Uehara; M Yokoyama
ALGORITHM AND COMPUTATION, PROCEEDINGS, SPRINGER-VERLAG BERLIN, 1969巻, 掲載ページ 338-349, 出版日 2001年, 査読付, Let G = (V, E) be an undirected multi-graph where V and E are a set of nodes and a set of edges, respectively. Let k and 1 be fixed nonnegative integers. This paper considers location problems of finding a minimum size of node-subset S subset of or equal to V such that node-connectivity between S and x is greater than or equal to k and edge-connectivity between S and x is greater than or equal to l for every x is an element of V. This problem has important applications for multi-media network control and design. For a problem of considering only edge-connectivity, i.e., k = 0, an O(L(\V \, \E \, l)) = O(\E \ + \V \ (2) + \V \ min{\E \, 1 \V \ }min{l, \V \}) time algorithm was already known, where L(\V \, \E \, l) is a time to find all h-edge-connected components for h = 1, 2,...,l. This paper presents an O(L(\V \, \E \, l)) time algorithm for 0 less than or equal to k less than or equal to 2 and l greater than or equal to 0. It also shows that if k greater than or equal to 3, the problem is NP-hard even for l = 0. Moreover, it shows that if the size of S is regarded as a parameter, the parameterized problem for k = 3 and l less than or equal to 1 is FPT (fixed parameter tractable).
研究論文（学術雑誌）, 英語 - レイリーフェージング通信路に有効な環上の畳込み符号
小西たつ美; 横山光雄; 上原秀幸; 伊藤大雄
信学論, J84-A巻, 3号, 掲載ページ 834--839, 出版日 2001年, 査読付
研究論文（学術雑誌）, 日本語 - 手数制限付き一般化詰め将棋のPSPACE 完全性について
横田雅也; 築地立家; 藤井愼二; 伊藤大雄
信学論, 一般社団法人電子情報通信学会, J84-D-I巻, 1号, 掲載ページ 58--61-61, 出版日 2001年, 査読付, 縦横Nますに王将を除く各駒がO(N)枚ずつ配置されている盤面が与えられたとき, 詰み手順があるかどうかを判定する問題を一般化つめ将棋問題と呼ぶ.伊藤らはその計算複雑さがNP困難であることを証明した.本論文では盤面とともに手数の上限を単進数で与えたときの一般化詰め将棋問題がPSPACE完全であることを証明する.
研究論文（学術雑誌）, 日本語 - Sum of edge lengths of a graph drawn on a convex polygon
H Ito; H Uehara; N Yokoyama
DISCRETE AND COMPUTATIONAL GEOMETRY, SPRINGER-VERLAG BERLIN, 2098巻, 掲載ページ 160-166, 出版日 2001年, 査読付, Let x(0),x(1),.... x(n-1) be vertices of a convex n-gon P in the plane, where, x(0)x(1), x(1)x(2),..., x(n-2)x(n-1), and x(n-1)x(0) are edges of P. Let G = (N, E) be a graph, such that N = {0. 1,..., n - 1}. Consider a graph drawing of G such that each vertex i is an element of N is represented by xi and each edge (i,j) is an element of E is drawn by a straight line segment.. Denote the sum of lengths of graph edges in such drawing by S-p(G). If S-p(G) less than or equal to Sp(G') for any convex n-gon P, then we write as G less than or similar toiota G'. This paper shows two necessary and sufficient conditions of G less than or similar toiota G'. Moreover, these conditions can be calculated in polynomial time for any given G and G'.
研究論文（学術雑誌）, 英語 - A faster and flexible algorithm for a location problem on undirected flow networks
H Ito; H Uehara; M Yokoyama
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, E83A巻, 4号, 掲載ページ 704-712, 出版日 2000年04月, 査読付, For a given graph G = (V, E), edge capacities c(e) for edges e is an element of E, and flow-demands d(v) for nodes v is an element of V, a problem of finding the minimum size source-set S subset of or equal to V such that the maximum flow-amount between S and v is greater than or equal to d(v) for every v is an element of V is called generalized plural cover problem (GPC). For this problem, O(np.s(n, m)) time algorithm is presented, where a, m, and p is the number of nodes, edges, and different values of d(v), respectively, and s(n, m) is the time required to solve the maximum flow problem of a graph with a nodes and m edges. This algorithm also constructs a set of optimal solutions in the same time. This property is convenient for applying it to real problems, because other constraints can also be taken into account.
研究論文（学術雑誌）, 英語 - NP-completeness of reallocation problems with restricted block volume
H Miwa; H Ito
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, E83A巻, 4号, 掲載ページ 590-597, 出版日 2000年04月, 査読付, A reallocation problem is defined as determining whether blocks can be moved from their current boxes to their destination boxes in the number of moves less than or equal to a given positive integer. This problem is defined simply and has many practical applications. We previously proved the following results: The reallocation problem such that the block volume is restricted to one volume unit for all blocks can be solved in linear time. But the reallocation problem such that the block volume is not restricted is NP-complete, even if no blocks have bypass boxes. But the computational complexity of the reallocation problems such that the range of the block volume is restricted has not yet been known. We prove that the reallocation problem is NP-complete even if the block volume is restricted to one or two volume units for all blocks and no blocks have bypass boxes. Furthermore, we prove that the reallocation problem is NP-complete, even if there are only two blocks such that each block has the volume units of fixed positive integer greater or equal than two, the volume of the other blocks is restricted to one volume unit, and no blocks have bypass boxes. Next, we consider such a block that must stays in a same box both in the initial state and in the final state but can be moved to another box for making room for other blocks. We prove that the reallocation problem such that an instance has such blocks is also NP-complete even if the block volume is restricted to one volume unit for all blocks.
研究論文（学術雑誌）, 英語 - NP-hardness of rotation type cell-mazes
S Aoki; H Ito; H Uehara; M Yokoyama; T Horinouchi
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, E83A巻, 3号, 掲載ページ 492-496, 出版日 2000年03月, 査読付, In paper, a puzzle called Cell-Maze is analyzed. In this puzzle, cells are arranged in checker board squares. Each cell is rotated when a play er arrives at the cell. Cell-Maze asks whether or not a player started from a start cell can reach a goal cell. The reachability problem for ordinary graphs can be easily solved in linear time, however a reachability problem for the network such as Cell-Maze may be extremely difficult. In this paper, NP-hardness of this puzzle is proved. It is proved by reducing Hamiltonian Circuit Problem of directed planar graph G such that each vertex involved in just three arcs. Furthermore, we consider subproblems, which can be solved in polynomial time.
研究論文（学術雑誌）, 英語 - Slot assignment scheme for integrated voice and data traffic in reservation-type packet radio networks
H Uehara; M Fujihara; M Yokoyama; Ito, I
PIMRC 2000: 11TH IEEE INTERNATIONAL SYMPOSIUM ON PERSONAL, INDOOR AND MOBILE RADIO COMMUNICATIONS, VOLS 1 AND 2, PROCEEDINGS, IEEE, 掲載ページ 222-226, 出版日 2000年, 査読付, In this paper, we propose a slot assignment scheme for integrated voice and data traffic in reservation multiple access protocol. In the proposed scheme, a voice packet does not contend with a data packet and takes over the slot which is previously assigned to a data packet. Thus, a larger number of voice terminals can be accommodated without degradation of quality and throughput even in the situation that data were integrated. We evaluate the voice packet dropping probability, throughput and packet delay through computer simulation. The results show that the proposed scheme has better performance than the conventional PRMA and DQRUMA systems.
研究論文（国際会議プロシーディングス）, 英語 - NP-completeness of stage illumination problems
H Ito; H Uehara; M Yokoyama
DISCRETE AND COMPUTATIONAL GEOMETRY, SPRINGER-VERLAG BERLIN, 1763巻, 掲載ページ 158-165, 出版日 2000年, 査読付, The stage illumination problem presented by Urrutia in 1992 is one of illumination problems, which uses floodlights for illuminating a stage. The problem asks whether or not it is possible to rotate given floodlights around their apexes so as to obtain a final configuration such that a given stage is completely illuminated. The problem for finding a polynomial time algorithm for this problem or proving NP-hardness of this problem was open. This paper shows that it is NP-complete even with some restrictions.
研究論文（学術雑誌）, 英語 - 2-dimension ham sandwich theorem for partitioning into three convex pieces
H Ito; H Uehara; M Yokoyama
DISCRETE AND COMPUTATIONAL GEOMETRY, SPRINGER-VERLAG BERLIN, 1763巻, 掲載ページ 129-157, 出版日 2000年, 査読付, Let m greater than or equal to 2, n greater than or equal to 2, and q greater than or equal to 2 be positive integers, Let S-r and S-b be hero disjoint sets of points in the plane such that no three points of S-r boolean OR S-b are collinear, \S-r\ = nq, and \S-b\ = mq. This paper shows that Kaneko and Kano's conjecture is true, i.e., S-r boolean OR S-b can be partitioned into q subsets P-1, P-2,... P-q satisfying that: (i) conv(P-i) boolean AND conv(P-j) = 0 for all 1 less than or equal to i < j < q; (ii) \P-i boolean AND S-r\ = n and \P-i boolean AND S-b\ = m for all 1 I i I a. This is a generalization of 2-dimension Hem Sandwich Theorem.
研究論文（学術雑誌）, 英語 - The sum of chord lengths for convex polygons is a concave and increasing function
ITO Hiro; UEHARA Hideyuki; YOKOYAMA Mitsuo
Proceedings of the Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, 掲載ページ 79--81, 出版日 1999年03月, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Access control schemes for slotted ALOHA system with an adaptive array
UEHARA Hideyuki; YOKOYAMA Mitsuo; ITO Hiro
Proceedings of the 1998 International Symposium on Information Theory and Its Application (ISITA'98), 掲載ページ 142--145, 出版日 1998年10月, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Linear time algorithms for graph search and connectivity determination on complement graphs
H Ito; M Yokoyama
INFORMATION PROCESSING LETTERS, ELSEVIER SCIENCE BV, 66巻, 4号, 掲載ページ 209-213, 出版日 1998年05月, 査読付, This paper presents a storage method to represent a simple undirected graph, that is, to maintain in a data structure the original graph if m less than or equal to n(n - 1)/4, and the complement graph if m > n(n - 1)/4. The paper also considers the linear time solvability of some problems based on this storage method. It shows that a breadth first search toe and a depth first search tree on the complement graph of a given graph can be constructed in linear time. It also shows that legal node ordering and sparse subgraphs preserving connectivity properties of the complement graph of a given graph can be found in linear time. By using this procedure, we can solve the problems on complement graphs for determining k-node (k-edge) connectivity for k less than or equal to 3, and constructing a minimal 2-node (2-edge) connected spanning subgraph in linear time. (C) 1998 Elsevier Science B.V. All rights reserved.
研究論文（学術雑誌）, 英語 - Sparse spanning subgraphs preserving connectivity and distance between vertices and vertex subsets
H Miwa; H Ito
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, E81A巻, 5号, 掲載ページ 832-841, 出版日 1998年05月, 査読付, This paper investigates the relations between the computational complexity and the restrictions for several problems that determine whether a given graph with edge costs and edge lengths has a spanning subgraph with such restrictions as the diameter, the connectivity, and the NA-distance and the NA-(edge)-connectivity proposed and investigated in [1]-[5]. The NA-distance and the NA-(edge)-connectivity are the measures for the distance and the connectivity between a vertex and a vertex subset (area). In this paper we prove that the minimum diameter spanning subgraph problem considering the restrictions of the diameter and the sum of edge costs is NP-complete even if the following restrictions are satisfied: all edge costs and all edge lengths are equal to one, and the upper bound of the diameter is restricted to four. Next, we prove that the minimum NA-distance spanning subgraph problem considering the restrictions of the NA-distances and the sum of edge costs is NP-complete even if the following conditions are satisfied: all edge costs and all edge lengths are equal to one, the upper bound of the NA-distance is restricted to four, each area is composed of a vertex, and the number of areas is restricted to two. Finally, we investigate the preserving NA-distance and NA-edge-connectivity spanning subgraph problem considering the preservations of the NA-distances and the NA-edge-connectivity and the restrictions of the sum of edge costs, and prove that a sparse spanning subgraph can be constructed in polynomial time if all edge costs are equal to one.
研究論文（学術雑誌）, 英語 - Edge connectivity between nodes and node-subsets
H Ito; M Yokoyama
NETWORKS, JOHN WILEY & SONS INC, 31巻, 3号, 掲載ページ 157-163, 出版日 1998年05月, 査読付, Let G = (V, E) be a graph where V and E are a set of nodes and a set of edges, respectively. Let X = {V-1, V-2,...V-rho} V-i subset of or equal to V be a family of node-subsets. Each node-subset V-i is called an area, and a pair of G and X is called an area graph. A node upsilon is an element of V and an area V-i is an element of X are called k-NA (node-to-area)-connected if the minimum size of a cut separating upsilon and V-i is at least k. We say that an area graph (G, X) is k-NA-edge-connected when each upsilon is an element of V and V-i is an element of X are k-NA-edge-connected. This paper gives a necessary and sufficient condition for a given (G, X) to be k-NA-edge-connected: (G, X) is k-NA-edge-connected iff, for all positive integers h less than or equal to k, every h-edge-connected component of G includes at least one node from each area or has at least k edges between the component and the rest of the nodes. This paper also studied the Minimum Area Augmentation Problem, i.e., the problem of determining whether or not a given area graph (G, X) is k-NA-edge-connected and of choosing the minimum number of nodes to be included in appropriate areas to make the area graph k-NA-edge-connected (if (G, X) is not k-NA-edge-connected). This problem can be regarded as one of the location problems, which arises from allocating service-nodes on multimedia networks. We propose an O(\E\ + \V\(2) + L' + min{\E\, k\V\}min{k\V\, k + \V\(2)}) time algorithm for solving this problem, where L' is a space required to represent output areas. For a fixed k, this algorithm also runs in linear time when the h-edge-connected components of G are available for all h = 1, 2,...,k. (C) 1998 John Wiley & Sons.
研究論文（学術雑誌）, 英語 - Repairing flaws in a picture based on a geometric representation of a digital image
T Asano; H Ito; S Kimura; S Shimazu
ALGORITHMS AND COMPUTATIONS, SPRINGER-VERLAG BERLIN, 1533巻, 掲載ページ 149-158, 出版日 1998年, 査読付, In high-quality image printing it is sometimes required to repair flaws contained in a given image;a simple way for such repair is to paste a flaw region with white and then to move those pixels in the neighborhood by using a tool called an copy-brush. Since it is a very fine operation, it causes great effort to human operators. It is not easy to automate this operation in the existing matrix representation of an image. In our geometric representation of an image as a collection of contour lines for intensity levels this problem is naturally defined as one of reconnecting those contour lines disconnected by a flaw region. An efficient algorithm for reconnecting contour lines is presented based on perfect matching and observations on geometric properties of interconnection paths.
研究論文（学術雑誌）, 英語 - A linear-time algorithm for determining the order of moving products in reallocation problems
H Miwa; H Ito
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, E80A巻, 3号, 掲載ページ 534-543, 出版日 1997年03月, 査読付, The reallocation problem is defined as determining whether products can be moved from their current storehouses to their target storehouses in a number of moves that is less than or equal to a given number. This problem is defined simply and has many practical applications. We previously presented necessary and sufficient conditions whether an instance of the reallocation problem is feasible, as well as a linear-time algorithm that determines whether all products can be moved, when the volume of the products is restricted to one. However, a linear-time algorithm that generates the order of moving the products has not been reported yet. Such an algorithm is proposed in this paper. We have also previously proved that the reallocation problem is NP-complete in the strong sense when the volume of the products is not restricted and the products have evacuation storehouses into which they can temporarily be evacuated [1]. In this paper we show that the reallocation problem is NP-complete in the strong sense even when none of the products has evacuation storehouses.
研究論文（学術雑誌）, 英語 - Complexity and algorithm for reallocation problem
H Miwa; H Ito
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, E79A巻, 4号, 掲載ページ 461-468, 出版日 1996年04月, 査読付, We define the Reallocation Problem to determine whether we can move products From their current store houses to target storehouses in a number of moves which is less than or equal to a given number. This problem is defined simply and can be applied to many practical problems. We give necessary and sufficient conditions for feasibility for Reallocation Problems under various conditions, and propose linear time algorithms, when the volume of the products is restricted to 1. Moreover, we show that the Reallocation Problem is NP-complete in the strong sense, when the volume of the products is not restricted.
研究論文（学術雑誌）, 英語 - Computational complexity of multicommodity flow problems with uniform assignment of flow
H Ito
ELECTRONICS AND COMMUNICATIONS IN JAPAN PART III-FUNDAMENTAL ELECTRONIC SCIENCE, SCRIPTA TECHNICA-JOHN WILEY & SONS, 78巻, 8号, 掲載ページ 52-62, 出版日 1995年08月, 査読付, This paper treats multicommodity flow problems with a flow assignment constraint. General multicommodity flow problems require both the path set in which the commodities are assigned and the volume to which the commodities are assigned for each path. However, in this paper, we treat only problems wherein paths are required. The flow is assigned to the paths uniformly. This problem appears in state-and-time-dependent routing (STR), which is a kind of dynamic routing scheme in telecommunication networks. We show that this problem is NP-complete and remains NP-complete if the lengths (number of edges) of paths are restricted to less than or equal to two but can be solved in polynomial time if the path lengths are restricted to be less than or equal to two and the number of commodities is fixed.
研究論文（学術雑誌）, 英語 - CONNECTIVITY PROBLEMS ON AREA GRAPHS FOR LOCALLY STRIKING DISASTERS - DIRECT NA CONNECTION
H ITO
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, E78A巻, 3号, 掲載ページ 363-370, 出版日 1995年03月, 査読付, Connectivity (of node-to-node) is generally used to examine the robustness of graphs. When telecommunication network switches are integrated into logical switching areas, we should examine node-to-area connectivity rather than node-to-node connectivity. In a previous paper, we proposed node-to-area (NA) connectivity using area (subset of nodes) graph. In this paper, we consider a further constraint: ''there is a path that does not include other nodes in the source node area.'' We call this property, directly NA-connected. Application of this constraint makes telecommunications networks robust against locally striking disasters. The problem of finding the maximum number of edge deletions that still preserves the direct NA-connection is shown to be NP-hard. It was shown in our previous paper that an NA-connected spanning tree is easily found; this paper shows that the problem of finding a directly NA-connected spanning tree is also NP-hard. We propose an O(\E parallel to X\) approximation algorithm that finds a directly NAconnected spanning subgraph with an edge number not exceeding 2\V\-3 for any NA-connected area graph that satisfies a described simple condition. (\V\, \E\, and \X\ are the numbers of nodes, edges, and areas, respectively.)
研究論文（学術雑誌）, 英語 - フロー割当によるネットワーク性能推定法
松崎隆一; 伊藤大雄
信学論, J78-B-I巻, 3号, 掲載ページ 825--836, 出版日 1995年, 査読付
研究論文（学術雑誌）, 日本語 - グラフにおける節点・領域連結度について
伊藤大雄
電気学会論文誌, 114-C巻, 4号, 掲載ページ 463--469-469, 出版日 1994年, 査読付
研究論文（学術雑誌）, 日本語 - Hybrid control strategies for advanced network control and their intelligent decision support system
INOUE Akiya; ITO Hiro; YAMAMOTO Hisao
Proceedings of the Fifth International Network Planning Symposium (NETWORKS'92), 掲載ページ 37--42, 出版日 1992年05月, 査読付
研究論文（国際会議プロシーディングス）, 英語 - ダイナミックルーチングのための迂回候補群作成法
伊藤大雄; 井上明也
信学論, J75-B-I巻, 5号, 掲載ページ 323--332-332, 出版日 1992年, 査読付
研究論文（学術雑誌）, 日本語 - 経由枝数に制限を持つ多品種流問題
伊藤大雄
信学論, J75-A巻, 3号, 掲載ページ 643--645, 出版日 1992年, 査読付
研究論文（学術雑誌）, 日本語 - ADVANCED CALL-LEVEL ROUTING SCHEMES FOR HYBRID CONTROLLED DYNAMIC ROUTING
A INOUE; H YAMAMOTO; H ITO; K MASE
IEICE TRANSACTIONS ON COMMUNICATIONS ELECTRONICS INFORMATION AND SYSTEMS, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, 74巻, 12号, 掲載ページ 4025-4033, 出版日 1991年12月, 査読付, A hybrid controlled dynamic routing scheme called State- and Time-dependent Routing (STR), has been proposed for telephone networks. The STR is characterized by two-level control processes: routing domain definition and call-level routing. In the routing domain definition, a set of possible alternate routes for each origin-destination node pair for each time period of the day is determined once a week by a centralized control method. In the call-level routing, each exchange determines a near-optimum alternate route from the set of possible alternate routes, which is determined in the routing domain definition process according to only the network information obtained in the call-connection processes. This paper proposes advanced call-level routing schemes for improving the performance of the basic STR. Call-by-call computer simulation of call-level routing schemes under imbalanced traffic conditions and focused overload conditions shows that the advanced schemes can achieve high performance with minimal changes of existing exchange software and operations systems. The performance of the advanced scheme based on isolated control capabilities built into each exchange is close to that of an ideal state-dependent scheme that is based on centralized control capabilities and uses data on the status of the entire network.
研究論文（学術雑誌）, 英語
MISC
- ましゅの定数時間検査
兜石鼓太郎; 伊藤大雄
ラスト(シニア)オーサー, 出版日 2024年03月, 信学技報, COMP2023巻, 2024-03号, 掲載ページ 14-21, 研究発表ペーパー・要旨（全国大会，その他学術会議） - ネコ教授が楽しむ数学・計算機科学講義
伊藤大雄
筆頭著者, 出版日 2024年01月, 数理解析研究所講究録, 2275巻, 掲載ページ 12-17, 招待 - Unfolding and Dissection of Multiple Cubes, Tetrahedra, and Doubly Covered Squares
Zachary Abel; Brad Ballinger; Erik D. Demaine; Martin L. Demaine; Jeff Erickson; Adam Hesterberg; Hiro Ito; Irina Kostitsyna; Jayson Lynch; Ryuhei Uehara
In this paper, we introduce the notion of "rep-cube": a net of a cube that can be divided into multiple polygons, each of which can be folded into a cube. This notion is inspired by the notion of polyomino and rep-tile; both are introduced by Solomon W. Golomb, and well investigated in the recreational mathematics society. We prove that there are infinitely many distinct rep-cubes. We also extend this notion to doubly covered squares and regular tetrahedra.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.25(2017) (online)DOI http://dx.doi.org/10.2197/ipsjjip.25.610------------------------------In this paper, we introduce the notion of "rep-cube": a net of a cube that can be divided into multiple polygons, each of which can be folded into a cube. This notion is inspired by the notion of polyomino and rep-tile; both are introduced by Solomon W. Golomb, and well investigated in the recreational mathematics society. We prove that there are infinitely many distinct rep-cubes. We also extend this notion to doubly covered squares and regular tetrahedra.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.25(2017) (online)DOI http://dx.doi.org/10.2197/ipsjjip.25.610------------------------------, 出版日 2017年08月15日, 情報処理学会論文誌, 58巻, 8号, 英語, 1882-7764, 170000148837, AN00116647 - A Much Faster Algorithm for Finding a Maximum Clique with Computational Experiments
Etsuji Tomita; Sora Matsuzaki; Atsuki Nagao; Hiro Ito; Mitsuo Wakatsuki
We present further improvements to a branch-and-bound maximum-clique-finding algorithm MCS (WALCOM 2010, LNCS 5942, pp.191-203) that was shown to be fast. First, we employ a variant of an efficient approximation algorithm KLS for finding a maximum clique. Second, we make use of appropriate sorting of vertices only near the root of the search tree. Third, we employ a lightened approximate coloring mainly near the leaves of the search tree. A new algorithm obtained from MCS with the above improvements is named k5_MCT. It is shown that k5_MCT is much faster than MCS by extensive computational experiments. In particular, k5_MCT is shown to be faster than MCS for gen400_p0.9_75, gen400_p0.9_65 and gen400_p0.9_55 by over 81,000, 39,000 and 19,000 times, respectively.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.25(2017) (online)DOI http://dx.doi.org/10.2197/ipsjjip.25.667------------------------------We present further improvements to a branch-and-bound maximum-clique-finding algorithm MCS (WALCOM 2010, LNCS 5942, pp.191-203) that was shown to be fast. First, we employ a variant of an efficient approximation algorithm KLS for finding a maximum clique. Second, we make use of appropriate sorting of vertices only near the root of the search tree. Third, we employ a lightened approximate coloring mainly near the leaves of the search tree. A new algorithm obtained from MCS with the above improvements is named k5_MCT. It is shown that k5_MCT is much faster than MCS by extensive computational experiments. In particular, k5_MCT is shown to be faster than MCS for gen400_p0.9_75, gen400_p0.9_65 and gen400_p0.9_55 by over 81,000, 39,000 and 19,000 times, respectively.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.25(2017) (online)DOI http://dx.doi.org/10.2197/ipsjjip.25.667------------------------------, 出版日 2017年08月15日, 情報処理学会論文誌, 58巻, 8号, 英語, 1882-7764, 170000148844, AN00116647 - Bumpy Pyramid Folding Problem (システム数理と応用)
ABEL ZACHARY R.; DEMAINE ERIK D.; DEMAINE MARTIN L.; ITO HIRO; SNOEYINK JACK; UEHARA RYUHEI
Folding problems are investigated for a class of petal (or star-like) polygons P, with an n-polygonal base B surrounded by a sequence of triangles for which adjacent pairs of sides have equal length. Linear time algorithms using constant precision are given to determine if P can fold to a pyramid with flat base B, and to determine a triangulation of B (crease pattern) that allows folding into a bumpy pyramid that is convex. By Alexandrov's theorem, the crease pattern is unique if it exists, but the general algorithm known for this theorem is pseudo-polynomial, with very large running time; ours is the first efficient algorithm for Alexandrov's theorem for a special class of polyhedra. We also show a polynomial time algorithm that finds the crease pattern to produce the maximum volume bumpy pyramid., 一般社団法人電子情報通信学会, 出版日 2013年11月06日, 電子情報通信学会技術研究報告 = IEICE technical report : 信学技報, 113巻, 279号, 掲載ページ 113-119, 英語, 0913-5685, 110009886695, AA12529664 - Bumpy Pyramid Folding Problem
ZacharyR.Abel; ErikD.Demaine; MartinL.Demaine; Hiro Ito; Jack Snoeyink; Ryuhei Uehara
Folding problems are investigated for a class of petal (or star-like) polygons P, with an n-polygonal base B surrounded by a sequence of triangles for which adjacent pairs of sides have equal length. Linear time algorithms using constant precision are given to determine if P can fold to a pyramid with flat base B, and to determine a triangulation of B (crease pattern) that allows folding into a bumpy pyramid that is convex. By Alexandrov's theorem, the crease pattern is unique if it exists, but the general algorithm known for this theorem is pseudo-polynomial, with very large running time; ours is the first efficient algorithm for Alexandrov's theorem for a special class of polyhedra. We also show a polynomial time algorithm that finds the crease pattern to produce the maximum volume bumpy pyramid.Folding problems are investigated for a class of petal (or star-like) polygons P, with an n-polygonal base B surrounded by a sequence of triangles for which adjacent pairs of sides have equal length. Linear time algorithms using constant precision are given to determine if P can fold to a pyramid with flat base B, and to determine a triangulation of B (crease pattern) that allows folding into a bumpy pyramid that is convex. By Alexandrov's theorem, the crease pattern is unique if it exists, but the general algorithm known for this theorem is pseudo-polynomial, with very large running time; ours is the first efficient algorithm for Alexandrov's theorem for a special class of polyhedra. We also show a polynomial time algorithm that finds the crease pattern to produce the maximum volume bumpy pyramid., 一般社団法人情報処理学会, 出版日 2013年10月30日, 研究報告アルゴリズム（AL）, 2013巻, 19号, 掲載ページ 1-7, 英語, 0919-6072, 110009614899, AN1009593X - On A Generalization of River Crossing Problems
Hiro Ito; Stefan Langerman; Yuichi Yoshida
出版日 2013年04月, Proc. 6th Annual Meeting of Asian Association for Algorithms and Computation (AAAC), 英語, 査読付, 研究発表ペーパー・要旨（国際会議） - Testing graph rigidity in constant time
Hiro Ito; Shin-ichi Tanigawa; Yuichi Yoshida
出版日 2011年04月, Proc. 4th Annual Meeting of Asian Association for Algorithms and Computation (AAAC), 英語, 研究発表ペーパー・要旨（国際会議） - ナップサック問題に対する定数時間近似アルゴリズム
伊藤 大雄; 清島 奨; 吉田 悠一
社団法人電子情報通信学会, 出版日 2011年03月, 電子情報通信学会技術研究報告. COMP, コンピュテーション, 110巻, 464号, 掲載ページ 29-36, 日本語, 0913-5685, 110008689181 - An almost optimal algorithm for Winkler's sorting pairs in bins (コンピュテーシヨン)
Ito Hiro; Teruyama Junichi; Yoshida Yuichi
We investigate the following sorting puzzle: We are given n bins with two balls in each bin. Balls in the ith bin are numbered n-i+1. We can swap two balls from adjacent bins. How many number of swaps are needed in order to sort balls, i.e., move every ball to the bin with the same number. For this puzzle the best known solution requires almost (4n^2)/5 swaps. In this paper, we show an algorithm which solves this puzzle using less than (2n^2)/3 swaps. Since it is known that the lower bound of the number of swaps is [numerical formula],our result is almost tight. Futhermore, we show that for n=2^k+1(k〓0) the algorithm is optimal., 一般社団法人電子情報通信学会, 出版日 2010年01月18日, 電子情報通信学会技術研究報告. COMP, コンピュテーション, 109巻, 391号, 掲載ページ 45-49, 英語, 0913-5685, 110008004172, AN10013152 - STOC2009参加報告
伊藤 大雄; 吉田 悠一
一般社団法人情報処理学会, 出版日 2009年08月15日, 情報処理, 50巻, 8号, 掲載ページ 794-797, 日本語, 0447-8053, 110007339758 - Constant-time approximations using minimum value search for independent sets and matchings
Yuichi Yoshida; Masaki Yamamoto; Hiro Ito
出版日 2009年04月, Proc. 2nd Annual Meeting of Asian Association for Algorithms and Computation (AAAC), 英語, 研究発表ペーパー・要旨（国際会議） - DS-1-1 最大独立集合と最大マッチングに対する定数時間近似アルゴリズムの改善(DS-1. COMP学生シンポジウム,シンポジウムセッション)
吉田 悠一; 山本 真基; 伊藤 大雄
社団法人電子情報通信学会, 出版日 2009年03月04日, 電子情報通信学会総合大会講演論文集, 2009巻, 1号, 掲載ページ "S-21"-"S-22", 日本語, 110007094594 - Property testing on k-vertex-connectivity of graphs (コンピュテーション)
吉田 悠一; 伊藤 大雄
最大頂点次数が与えられた定数以下の無向グラフのk点連結性を検査するアルゴリズムを示す。このアルゴリズムの計算量は入力グラフの頂点数、枝数に依らない定数である。頂点数n、最大次数dのグラフGがk点連結性からε遠隔であるとは、そのグラフを最大頂点次数がd以下のk点連結なグラフに変形するのに、少なくともεdn/2本の枝を追加および削除しなければならないことを言う。本アルゴリズムはグラフがk点連結のときは常にグラフを受理し、グラフがk点連結性からε遠隔であるときは、確率2/3以上で拒否する。計算時間は、入力グラフがk-1点連結なものに限定されている時、O(d(c/(εd))^klog1/(εd))(c>1は定数)時間であり、入力グラフが一般のときはO(d((ck)/(εd))^klogk/(εd))(c>1は定数)時間である。本アルゴリズムは一般のk≧4に対してk点連結性を定数時間で検査する初めてのアルゴリズムである。, 一般社団法人電子情報通信学会, 出版日 2008年06月16日, 電子情報通信学会技術研究報告, 108巻, 89号, 掲載ページ 49-55, 英語, 0913-5685, 110006951168, AN10013152 - On k-connectivity testing in degree-bounded graphs
Yuichi Yoshida; Hiro Ito
出版日 2008年04月, Proc. 1st Annual Meeting of Asian Association for Algorithms and Computation (AAAC), 英語, 研究発表ペーパー・要旨（国際会議） - 有向グラフにおけるk枝連結性の検査
吉田 悠一; 伊藤 大雄
社団法人電子情報通信学会, 出版日 2007年06月, 電子情報通信学会技術研究報告. COMP, コンピュテーション, 107巻, 127号, 掲載ページ 17-23, 日本語, 0913-5685, 110006343677 - Efficient Methods for Determining DNA Probe Orders
ITO Hiro; IWAMA Kazuo; TAMURA Takeyuki
In STS-based mapping, it is necessary to obtain the correct order of probes in a DNA sequence from a given set of fragments or an equivalently a hybridization matrix A. It is well-known that the problem is formulated as the combinatorial problem of obtaining a permutation of A's columns so that the resulting matrix has a consecutive-one property. If the data (the hybridization matrix) is error free and includes enough information, then the above column order uniquely determines the correct order of the probes. Unfortunately this does not hold if the data include errors, and this has been a popular research target in computational biology. Even if there is no error, ambiguities in the probe order may still remain. This in fact happens because of the lack of some information regarding the data, but almost no further investigation has previously been made. In this paper, we define a measure of such imperfectness of the data as the minimum amount of the additional fragments that are needed to uniquely fix the probe order. Polynomial-time algorithms to compute such additional fragments of the minimum cost are presented. A computer simulation using genes of human chromosome 20 is also noted., 一般社団法人電子情報通信学会, 出版日 2006年05月01日, IEICE transactions on fundamentals of electronics, communications and computer sciences, 89巻, 5号, 掲載ページ 1292-1298, 英語, 0916-8508, 110007502843, AA10826239 - グラフの変形操作における単純性の保存
伊藤大雄
ラベル付きグラフ上の半順序関係である、カットサイズ順序、枝長和順序、交叉操作順序の三つは同値であることが知られている。グラフGがこの半順序関係においてG'に先行するとき、GをG'に変形する交叉操作の列が存在するが、仮にGとG'の両方が単純グラフだとしても、中間に単純でないグラフが現れる可能性がある。このことは、Hakimiによる名高い次数不変変換においても同様に起こる問題である。本稿では、このような場合に単純グラフのみを介して、変形しうるか否かという問題を取り扱う。結果、Hakimiの次数不変変換については、常に単純グラフによる変形が可能であることを示した。しかし一方で、上記の半順序関係に基づく変形の場合は、例え交叉操作以外の操作も許容したとしても、与えられた操作の種類が有限だとすると、その半順序関係にありながら単純グラフのみを介しての変換ができないグラフの組が必ず存在することを証明した。Three partial orders, cut-size order, length order, and operation order, defined between labeled graphs with the same order are known to be equivalent. If G precedes G' with regard to the partial order, there is a sequence of cross-operations such that G is transformed into G' by using the sequence. Even if both G and G' are simple graphs, non-simple graphs may appear on the way of the transformation. The same problem occurs in the well-known Hakimi's d-invariant transformation. This paper considers whether we can transform them without using non-simple graphs. First, we show that we can do it in Hakimi's $d$-invariant transformation. Second, however, we prove that there is no efficient finite set of operations for the partial order's transformation in the general case., 一般社団法人情報処理学会, 出版日 2004年11月05日, 情報処理学会研究報告アルゴリズム（AL）, 2004巻, 109号, 掲載ページ 1-8, 英語, 0919-6072, 110002812555, AN1009593X ^^^--Coloring Problem
UEJIMA Akihiro; ITO Hiro; TSUKIJI Tatsuie
H-coloring problem is a coloring problem with restrictions such that some pairs of colors cannot be used for adjacent vertices, where H is a graph representing the restrictions of colors. We deal with the case that H is the complement graph^^^--coloring problem on planar graphs is_NP-complete, and (3) there exists a class that includes infinitely many ^^^--colorable but non-3-colorable planar graphs., 一般社団法人電子情報通信学会, 出版日 2004年05月01日, IEICE transactions on fundamentals of electronics, communications and computer sciences, 87巻, 5号, 掲載ページ 1243-1250, 英語, 0916-8508, 110003213026, AA10826239 - H-彩色可能なグラフのクラスの階層構造のCirculant graphs による細分化
上嶋 章宏; 伊藤大雄
p-彩色可能なグラフはC_{2p+1}-彩色可能であり，C_{2p+1}-彩色可能なグラフはp+1-彩色可能であるが，いずれも逆は成立しない(但しC_{2p+1}は長さ2p+1の閉路の補グラフである)．本発表ではこの包含関係が circulant graphsの部分集合として我々が定義するH(n k)によってさらに細分化されることを示す．この細分化は、従来から知られているC_{2p+1}による細分化をも包含する．更に平面グラフのH(n k)-彩色に対し，いくつかのNP-完全問題を示す．p-colorable graphs are C_{2p+1}-colorable, and C_{2p+1}-colorable graphs are p+1-colorable, where C_{2p+1} is the complement graph of a cycle of order 2p+1. However, the converse statements are incorrect. This paper presents that these inclusions can be subdivided by our original graphs H(n, k) which are defined as a subset of circulant graphs. The subdivided hierarchy contains the well-known inclusion of C_{2p+1}-colorable graphs. Moreover, This paper shows some NP-complete problems for planar H(n, k)-colorings., 一般社団法人情報処理学会, 出版日 2004年01月30日, 情報処理学会研究報告アルゴリズム（AL）, 2004巻, 10号, 掲載ページ 1-8, 日本語, 0919-6072, 110002811976, AN1009593X - 平面グラフのC7－彩色問題
上嶋 章宏; 伊藤大雄
本稿では，グラフの点彩色問題の一般化である，H-彩色問題を扱う(但し，Hはグラフ)．特にHが奇数長閉路の補グラフC￣_p(pは節点数)である場合を取り上げ，以下の性質を示す：(1) m-彩色可能であるとき，かつそのときに限り，C￣￣￣￣_2m+1-彩色可能であるような、グラフのクラスの提示，(2) 平面グラフのC￣_7-彩色問題の NP-完全性の証明，(3) C￣_7-彩色可能であるが，3-彩色不可能な平面グラフのクラスの提示．This paper considers H-coloring problem, which is a generalization of the traditional coloring problem, where H is a graph. Especially, we deal with the case that H is the complement graph C￣_p of a cycle of order p. This paper presents as follows: (1) classes of graphs which are C￣￣￣￣_2m+1-colorable iff m-colorable, (2) C￣_7 -coloring problem of planar graphs is NP-complete, and (3) there exists a class of graphs which are not 3-colorable but C￣_7-colorable., 一般社団法人情報処理学会, 出版日 2002年09月19日, 情報処理学会研究報告アルゴリズム（AL）, 2002巻, 88号, 掲載ページ 67-74, 日本語, 0919-6072, 110002812525, AN1009593X - グラフの平面凸描画の枝長と線形カットサイズと交差操作の関係
伊藤大雄
G = (N c)を節点集合N={0 1 ... n-1}と実数の枝の重み関数c:V×V->Rによって定義されるグラフ（ネットワーク）とする。以下の３つの尺度を考える。(1) 凸多角形上にグラフを記述したときの枝長の総和、(2) 線形カットの大きさ、(3) 枝の交差処理による帰着可能性。これらの３つの尺度に関連した半順序関係を導入し、それらが同値であることを証明する。Let G=(N,c) be a graph with a vertex set N={0,1,...,n-1} and a real edge weight function c:V×V->R. Three measures for comparing two graphs are considered: (1) the sum of edge length when the graph is drawn on a convex polygon, (2) sizes of linear-cuts, and (3) reducibility by using cross-operations. Three partial orders, corresponding the measures respectively, are also introduced. This paper shows that these three partial orders are equivalent. Moreover, it presents a polynomial time algorithm for determining G \preceq G' for given G and G', where, \preceq is the partial order., 一般社団法人情報処理学会, 出版日 2002年03月15日, 情報処理学会研究報告アルゴリズム（AL）, 2002巻, 29号, 掲載ページ 27-34, 日本語, 0919-6072, 110002812482, AN1009593X - Variable Rate MPSK Coded Modulation Using Convolutional Codes over Modules
KONISHI Tatsumi; YOKOYAMA Mitsuo; UEHARA Hideyuki; ITO Hiro
In this paper, we present a new method of a variable rate MPSK coded modulation using convolutional codes over modules. We define convolutional codes over modules, and investigate some properties of the codes such as the minimum Euclidean distance and the minimum Hamming distance. If any suitable module is selected for a variable rate coded modulation system, only a single encoder and a Viterbi decoder are sufficiently to support the variable rate modulation system. Coded modulation system using new convolutional codes over Z_<12> module are evaluated by computer simulation on AWGN and Rayleigh fading channels., 一般社団法人電子情報通信学会, 出版日 2002年03月01日, IEICE transactions on fundamentals of electronics, communications and computer sciences, 85巻, 3号, 掲載ページ 729-730, 英語, 0916-8508, 110003216806, AA10826239 - 優先領域に基づく中継制御法を用いたマルチホップ無線ネットワークの検討
北岸 弓子; 上原 秀幸; 横山 光雄; 伊藤 大雄
マルチホップ無線ネットワークにおけるパケット配信方式の一つにフラッディング方式がある.従来のフラッディング方式では, パケットを受信した全ての端末が中継を行うためにネットワーク内のトラヒックが増加するという問題がある.トラヒックの増加は競合や衝突の増加にもつながり, パケットの到達率やスループットの劣化をまねく.本報告では優先領域に基づいて冗長なパケットの中継を制限する中継制御法を提案する.計算機シミュレーションによって性能評価を行った結果, 提案する中継制御法を用いることによってネットワーク内のトラヒックを削減し, メッセージパケットの配信率, ルート確保率を向上させることができることを示す., 一般社団法人電子情報通信学会, 出版日 2002年01月04日, 電子情報通信学会技術研究報告. DSP, ディジタル信号処理, 101巻, 539号, 掲載ページ 15-20, 日本語, 0913-5685, 110003280587, AN10060786 - 優先領域に基づく中継制御法を用いたマルチホップ無線ネットワークの検討
北岸 弓子; 上原 秀幸; 横山 光雄; 伊藤 大雄
マルチホップ無線ネットワークにおけるパケット配信方式の一つにフラッディング方式がある.従来のフラッディング方式では, パケットを受信した全ての端末が中継を行うためにネットワーク内のトラヒックが増加するという問題がある.トラヒックの増加は競合や衝突の増加にもつながり, パケットの到達率やスループットの劣化をまねく.本報告では優先領域に基づいて冗長なパケットの中継を制限する中継制御法を提案する.計算機シミュレーションによって性能評価を行っ結果, 提案する中継制御法を用いることによってネットワーク内のトラヒックを削減し, メッセージパケットの配信率, ルート確保率を向上させることができることを示す., 一般社団法人電子情報通信学会, 出版日 2002年01月04日, 電子情報通信学会技術研究報告. RCS, 無線通信システム, 101巻, 545号, 掲載ページ 15-20, 日本語, 0913-5685, 110003305994, AN10060822 - 優先領域に基づく中継制御法を用いたマルチホップ無線ネットワークの検討
北岸 弓子; 上原 秀幸; 横山 光雄; 伊藤 大雄
マルチホップ無線ネットワークにおけるパケット配信方式の一つにフラッディング方式がある.従来のフラッディング方式では, パケットを受信した全ての端末が中継を行うためにネットワーク内のトラヒックが増加するという問題がある.トラヒックの増加は競合や衝突の増加にもつながり, パケットの到達率やスループットの劣化をまねく.本報告では優先領域に基づいて冗長なパケットの中継を制限する中継制御法を提案する.計算機シミュレーションによって性能評価を行っ結果, 提案する中継制御法を用いることによってネットワーク内のトラヒックを削減し, メッセージパケットの配信率, ルート確保率を向上させることができることを示す., 一般社団法人電子情報通信学会, 出版日 2002年01月03日, 電子情報通信学会技術研究報告. SAT, 衛星通信, 101巻, 542号, 掲載ページ 15-20, 日本語, 0913-5685, 110003193844, AN10012987 - A Faster and Flexible Algorithm for a Location Problem on Undirected Flow Networks
ITO Hiro; UEHARA Hideyuki; YOKOYAMA Mitsuo
For a given graph G=(V, E), edge capacities c(e) for edges e ⋳ E, and flow-demands d(v) for nodes v ⋳ V, a problem of finding the minimum size source-set S ⊊ V such that the maximum flow-amount between S and v is greater than or equal to d(v) for every v ⋳ V is called generalized plural cover problem (GPC). For this problem, O(np・s(n, m)) time algorithm is presented, where n, m, and p is the number of nodes, edges, and different values of d(v), respectively, and s(n, m) is the time required to solve the maximum flow problem of a graph with n nodes and m edges. This algorithm also constructs a set of optimal solutions in the same time. This property is convenient for applying it to real problems, because other constraints can also be taken into account., 一般社団法人電子情報通信学会, 出版日 2000年04月25日, IEICE transactions on fundamentals of electronics, communications and computer sciences, 83巻, 4号, 掲載ページ 704-712, 英語, 0916-8508, 110003208579, AA10826239 - 一般化詰め将棋問題の計算複雑さ : 小駒図式、成駒無し、還元玉、都詰の考慮
伊藤 大雄; 藤井 愼二; 上原 秀幸; 横山 光雄
詰め将棋の盤面をn×nにし、王将以外の駒を0(n)個の用意した、一般化詰め将棋問題の計算複雑さについて論じる。詰め将棋には見た目や詰め方などに面白みを出すため、駒の初期配置に工夫をしたり、正解の詰め手順に美しい趣向が隠されている様な、趣向詰めというものがある。本稿では、飛車と角を使用しない「小駒図式」、初期配置に成り駒が無い「成り駒無し」、王将が初期配置で居た場所に戻って詰む「還元玉」、王将が中央のマスで詰む「都詰め」の4つの趣向を同時に満たすものに限定しても一般化詰め将棋問題がNP困難であることを証明する。, 一般社団法人電子情報通信学会, 出版日 1999年07月21日, 電子情報通信学会技術研究報告. COMP, コンピュテーション, 99巻, 194号, 掲載ページ 17-24, 日本語, 0913-5685, 110003191783, AN10013152 - 遠近問題を考慮した送信許可確率可変スロットアロハ方式の検討
森山 崇元; 上原 秀幸; 横山 光雄; 伊藤 大雄
スロットアロハ方式等のパケット無線ネットワークにおけるスループット特性向上の手法としてのアクセス制御方式がいくつか提案されているが、このようなスループット向上は全ての端末に平等に与えられるわけではない。遠近問題を考慮した場合、基地局に近い端末に比べ、遠いところになる端末のスループットが著しく劣化するという不平等が生じる。そこで本稿では遠近問題を考慮したスロットアロハ方式において、チャネルロードに応じてパケット送信許可確率を適応的に変化させることにより、チャネルロードが大きいところでも最大スループットを維持しつつ、かつ基地局に近い端末と遠い端末の間で同等のスループット特性が得られることを計算機シミュレーションにより示す。, 一般社団法人電子情報通信学会, 出版日 1998年08月20日, 電子情報通信学会技術研究報告. SSE, 交換システム, 98巻, 240号, 掲載ページ 73-78, 日本語, 0913-5685, 110003235127, AN10060742 - 遠近問題を考慮した送信許可確率可変スロットアロハ方式の検討
森山 崇元; 上原 秀幸; 横山 光雄; 伊藤 大雄
スロットアロハ方式等のパケット無線ネットワークにおけるスループット特性向上の手法としてのアクセス制御方式がいくつか提案されているが、このようなスループット向上は全ての端末に平等に与えられるわけではない。遠近問題を考慮した場合、基地局に近い端末に比べ、遠いところになる端末のスループットが著しく劣化するという不平等が生じる。そこで本稿では遠近問題を考慮したスロットアロハ方式において、チャネルロードに応じてパケット送信許可確率を適応的に変化させることにより、チャネルロードが大きいところでも最大スループットを維持しつつ、かつ基地局に近い端末と遠い端末の間で同等のスループット特性が得られることを計算機シミュレーションにより示す。, 一般社団法人電子情報通信学会, 出版日 1998年04月23日, 電子情報通信学会技術研究報告. RCS, 無線通信システム, 98巻, 20号, 掲載ページ 73-78, 日本語, 110003305076, AN10060822 - 各節点の需要が異なる最小流入点集合配置問題
伊藤 大雄; 横山 光雄
各枝e∈Eに容量c(e)が与えられたフローネットワーク(G=(V,E),c)と各節点v∈Vの需要d(v)が与えられたとき、任意のv∈Vに対しv,T間の最大流がd(v)以上となるT⊆Vで要素数|T|が最小であるものを求める問題、最小流入点集合配置問題(Minimum size flow-sink-set location problem; FSSL)に対しO(np s(n,m))時間の解法を与えた。但しn,mは各々節点数と枝数、pはd(v)のうち異なるものの数、s(n,m)は2点間の最大流を求めるのに要する時間である。, 一般社団法人電子情報通信学会, 出版日 1997年05月30日, 電子情報通信学会技術研究報告. COMP, コンピュテーション, 97巻, 83号, 掲載ページ 41-48, 英語, 110003191267, AN10013152 - （n-p）-点連結性のO（m+np3.5）時間判定法
伊藤大雄; 横山 光雄
与えられたグラフG=(，)、整数1〓p〓nに対し、Gが(?)?点連結であるか否かを判定し、(?)?点連結である場合にはその点連結度も計算するO(+np^<3．5>）時間のアルゴリズムを与える（但しn=|V|，m=|E|）。また、与えられたグラフの点連結度を計算するO(+n(?K(））^<3．5>）時間のアルゴリズムも与える。これら2つのアルゴリズムはそれぞれ同じ計算時間のオーダーで、与えられたグラフの補グラフG^cに関して(?)?点連結性の判定や点連結度の計算問題を解くアルゴリズムにも拡張できる。For a given graph G=(V,E) and a given integer 1〓p〓n, an O(m+np^<3.5>) time algorithm for determining whether or not G is (n-p)-node-connected and also calculating the node-connectivity when G is (n-p)-node-connected is presented, where n=|V| and m=|E|. For calculation of the node-connectivity of a given graph G, an O(m+n(n-K(G))^<3.5>) time algorithm is also presented. These two algorithms can be extended to the same problems on the complement graph of a given graph in the same time-complexity, respectively., 一般社団法人情報処理学会, 出版日 1996年10月17日, 情報処理学会研究報告アルゴリズム（AL）, 1996巻, 100号, 掲載ページ 57-64, 日本語, 0919-6072, 110002812266, AN1009593X - フロー割当てによるダイナミックルーチング網設計法
佐竹 孝; 伊藤 大雄; 井上 明也
ダイナミックルーチング(DR)を考慮したフロー割当てによる回線数算出法を提案する。本手法の特徴は、(1)直通路からの許容あふれ率を規定して回線数を算出する、(2)時間帯や曜日による定常的なトラヒック変動を前提とし、迂回路での疎通トラヒック量を考慮して回線数を算出する、(3)DR導入網を運用・管理していくために直通路, 迂回路それぞれで運ばれるトラヒック量を把握することが容易となる、ことである。また、例としてSTR(State-and Time-dependent Routing)網に本手法を適用し、計算機実験により直通設計と比較して回線数削減効果が得られることを示す。, 一般社団法人電子情報通信学会, 出版日 1993年10月22日, 電子情報通信学会技術研究報告. IN, 情報ネットワーク, 93巻, 291号, 掲載ページ 43-50, 日本語, 110003196095, AN10013072 - フロー割当によるネットワーク性能推定法の評価
松崎 隆一; 伊藤 大雄
ダイナミックルーチング制御を有する回線交換網の設計・管理のために、「網機構条件、トラヒック条件、ルーチング条件を入力として、各回線群上にどの対地間交流呼量がどれだけ流れるかを算出する」問題を解くことが重要である。実網が大規模かつ複雑であることを考慮して、発見的なフロー割当手法の適用により、高速に計算する解法を提案する。本解法は厳密に関係式で表現できない場合にも適用でき、網条件の変化等で解法が影響を受けにくいという利点がある。数値実験により、提案手法の有効性を検証する。, 一般社団法人電子情報通信学会, 出版日 1993年10月01日, 電子情報通信学会技術研究報告. SSE, 交換システム, 93巻, 257号, 掲載ページ 135-140, 日本語, 0913-5685, 110003235016, AN10060742 - STR網におけるトラヒック流推定のためのフロー割当法の検討
松崎隆一; 伊藤大雄; 井上明也
出版日 1993年, 電子情報通信学会大会講演論文集, 1993巻, Shunki Pt 3号, 1349-1369, 200902120344424150 - ダイナミックルーチングSTRを考慮した回線算出法
佐竹孝; 伊藤大雄; 井上明也
出版日 1993年, 電子情報通信学会大会講演論文集, 1993巻, Shuki Pt 3号, 1349-1369, 200902145349858002 - 特集 ディジタル中継網におけるダイナミックルーチング方式の開発 ダイナミックルーチング(STR)の自律的迂回ルート選択機能とその性能評価
井上明也; 伊藤大雄
出版日 1992年, NTT R & D, 41巻, 6号, 0915-2326, 200902016074400480 - ルーチングにおけるハイブリッド制御の効果
伊藤大雄; 井上明也
出版日 1992年, 電子情報通信学会大会講演論文集, 1992巻, Shunki Pt 3号, 1349-1369, 200902058704730586 - 迂回候補群作成問題に関する発見的算法の効果 LPを用いた解法との比較
伊藤大雄; 井上明也
出版日 1991年, 電子情報通信学会全国大会講演論文集, 1991巻, Spring Pt 3号, 200902064613874488 - STRにおける迂回候補群作成法の予測誤り耐力の評価
伊藤大雄; 井上明也
出版日 1991年, 電子情報通信学会大会講演論文集, 1991巻, Shuki Pt 3号, 1349-1369, 200902068983630516 - 電話網における迂回候補群作成アルゴリズム
伊藤大雄; 井上明也
出版日 1990年, 電子情報通信学会技術研究報告, 89巻, 418(IN89 113-121)号, 0913-5685, 200902002701244782 - 電話網における迂回候補群作成アルゴリズム
伊藤大雄; 井上明也
出版日 1990年, 電子情報通信学会全国大会講演論文集, 1990巻, Spring Pt.3号, 200902064111600449
書籍等出版物
- イラストで学ぶ離散数学
伊藤大雄
教科書・概説・概論, 日本語, 単著, 講談社, 出版日 2019年09月07日, ISBN 9784065170014 - データ構造とアルゴリズム（コンピュータサイエンス教科書シリーズ ２）
伊藤大雄
教科書・概説・概論, 日本語, 単著, コロナ社, 出版日 2017年09月28日, ISBN 9784339027020 - ビッグデータ・マネジメント --- データサイエンティストのためのデータ利活用技術と事例
嶋田茂; 伊藤大雄
一般書・啓蒙書, 日本語, 共著, 第１編 第１章 第１節 ビッグデータの高速処理に向けた超高速アルゴリズムと計算理論, （株）エヌ・ティー・エス, 出版日 2014年03月10日, ISBN 9784864690843 - 離散数学のすすめ
伊藤大雄; 宇野裕之; 伊藤大雄; 名 著
一般書・啓蒙書, 日本語, 編者(編著者), 編集 および まえがき プロローグ「離散数学へのいざない」 第４章「最短路問題」 第７章「ケーキ分割問題」 第９章「フランク・ハラリィの一般化三並べ」 エピローグ「論文のできるまで --- 一般化ハムサンドイッチ定理を題材にして」 あとがき, 現代数学社, 出版日 2010年05月 - パズル・ゲームで楽しむ数学 --- 娯楽数学の世界
伊藤大雄
日本語, 単著, 森北出版, 出版日 2010年02月 - 離散幾何学における未解決問題集
秋山仁; 伊藤大雄; 訳
日本語, 共訳, 第３章「相似コピーによる詰め込みと被覆」, シュプリンガー・ジャパン, 出版日 2009年 - アルゴリズム工学 --- 計算困難問題への挑戦
杉原厚吉; 茨木俊秀; 浅野孝夫; 山下雅史; 伊藤大雄
日本語, 共著, 4.10節 「２次元ハムサンドイッチ定理の一般化」, 共立出版, 出版日 2001年06月 - ネットワーク設計理論（岩波講座「インターネット」第５巻）
滝根哲哉; 伊藤大雄; 西尾章治郎
日本語, 共著, 第４章「グラフ・ネットワークアルゴリズムの基本知識」 第５章「ネットワーク構成問題」, 岩波書店, 出版日 2001年06月
講演・口頭発表等
- Sublinear-Time Paradigm --- How to Challenge Big Data
Hiro Ito
口頭発表（基調）, 英語, The 13th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2019), 招待, 国際会議
発表日 2019年12月13日 - Generalized shogi and chess are constant-time tastable
Hiro Ito
口頭発表（招待・特別）, 英語, The 12th International Symposium on Operations Research & Its Applications (ISORA 2015), 招待, 国際会議
発表日 2015年08月 - Transformation of Graphs and their Simpleness
Hiro Ito
口頭発表（招待・特別）, 英語, he Japan Conference on Discrete and Computational Geometry 2004, 招待, 国際会議
発表日 2004年10月
共同研究・競争的資金等の研究課題
- 劣線形時間パラダイムの展開
伊藤 大雄
日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(C), 本研究では研究代表者の提案している「劣線形時間パラダイム」を広く展開するための理論研究を行っている。２０２１年度の主な成果は以下の通りである。 (I) 漸進型アルゴリズム(progressive algorithm)の結果をまとめた論文が論文誌に採録・出版された。「漸進型アルゴリズム」とは、データを徐々に読み込みながら段々と精度の高い解を求めていく手法であり、研究代表者によって提案されたものである。我々はこれまでに、「定数時間アルゴリズム」と「全てのデータを読み込む線形以上の計算時間のアルゴリズム」の両者が存在する任意の問題に対し、オーダの意味での各々の計算時間を悪化させることなく、両者を円滑に繋げる漸進型アルゴリズムが構築できることを証明した。これは片側誤り、両側誤りどちらにも適用可能であり、また本技法はグラフに限らず、どのような対象、モデルに対しても適用可能であると考えられ、非常に一般性のある結果である。(II) 機器をスリープ状態にしておくことで再起動の際の時間やエネルギー消費量の節減を図る制御は広く行われている。しかしスリープ状態は少しだが電力を消費し続けるので、長く保つと逆に損になる。この問題はオンライン問題の一種の「スキーレンタル問題」という形で定式化され、その競合比（小さいほど良く、１が最適）は２でこれ以上改善出来ないことが既存研究によって証明され、それが常識とされてきた。しかしその競合比２を与えるアルゴリズムは、最悪に備える為に多くの場合で明らかに無駄と考えられる動作をせざるを得なかった。そこで担当者は、競合比を2+ε（∀ε>0）と僅かに緩和することで、多くの実用的な場合にほぼ無駄が無い様に制御する方法を考案した。その結果を論文誌に投稿し採録・出版された。, 20K11671
研究期間 2020年04月01日 - 2023年03月31日 - 効率的な最大および極大クリーク抽出アルゴリズムの開発と応用
富田 悦次; 若月 光夫; 西野 哲朗; 伊藤 大雄
日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(C), 最大クリーク厳密解抽出の分枝限定アルゴリズムに対するこれまでの研究により，最大クリークの近似解が非常に有効に活用出来ることを明らかにしてきている．その近似精度が良くなれば分枝限定はより有効に働く．しかし，近似解抽出のために時間を要すると，総実行時間としては必ずしも短縮とはならず，近似精度と時間との兼ね合いが重要となる．そこで先ず，最大クリーク近似解の抽出を一層高速化し，その上で精度を向上させることにより，総合的に最大クリーク厳密解抽出を効率化した． 続いて，分枝限定のために近似彩色だけでなくMaxSATも用いることにより分枝限定がより強力化されることをこれまでに確認してきたが，MaxSATあるいはその簡略形実行のためのオーバーヘッドの大きさが最大クリーク厳密解抽出総実行時間短縮の妨げとなっていた．これに対しては，MaxSATの簡略形と従来提唱してきていた再番号付け（再彩色）との類似性に着目して両者を融合させることにより，これまでよりも少ないオーバーヘッドによって，有効な分枝限定効果を発揮出来るようにした．さらに，分枝限定アルゴリズムの内部動作は入力グラフの特徴に応じて効率が左右されるため，出来る限り効率がより発揮されるようにと内部動作を適応的に切り替えるようにした． 以上を総合することにより，最大クリーク厳密解抽出のための従来の分枝限定アルゴリズムを有意に高速化することに成功した． このような最大クリーク厳密解抽出アルゴリズムは，容易に最大クリーク全列挙アルゴリズムへと拡張出来る．これにより，符号理論における最良な多元単一削除訂正符号の構成に関しての新たな知見を得ることが出来た． 極大クリーク全列挙問題についてもさらに理論的，実験的に検討を続け，有効な進展結果を得た．, 17K00006
研究期間 2017年04月01日 - 2022年03月31日 - 劣線形時間パラダイム
伊藤 大雄
日本学術振興会, 科学研究費助成事業, 電気通信大学, 挑戦的萌芽研究, 本研究では、「劣線形時間パラダイム」の基本技術の確立を目的として行った。本研究期間における顕著な成果は、WebやSNSなど、複雑ネットワークと呼ばれる現実的な巨大グラフに対する万能定数時間アルゴリズムの提案である。すなわち、複雑ネットワークをモデル化したHSF (Hierarchical Scale Free) というマルチグラフの無限集合を定義し、それに対しては任意の性質が定数時間検査可能であることを証明した。これは疎でありかつ次数上限を持たない、所謂一般グラフと呼ばれる枠組みの非自明なクラスに対する初めての万能定数時間アルゴリズムである。, 15K11985
研究期間 2015年04月01日 - 2019年03月31日 - 最大および極大クリーク抽出アルゴリズムの高効率化と応用
富田 悦次; 若月 光夫; 西野 哲朗; 伊藤 大雄
日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(C), 最大クリーク抽出のための分枝限定アルゴリズムに対し，近似最大クリーク抽出アルゴリズムを効果的に組合せ，さらに節点整列と近似彩色を適切に適用することにより，実働上一層の高効率化を達成した．また理論的には，最大クリーク問題が多項式時間的高速に可解となる，よりゆるやかな条件およびアルゴリズムを与えた． 極大クリーク全列挙アルゴリズムについては，それを疑似極大クリークの全列挙までを扱えるように拡張し，ネットワーク解析への応用に対して有効性が確認された．, 25330009
研究期間 2013年04月01日 - 2018年03月31日 - 情報理論・符号理論からの計算限界研究
河原林 健一; 脊戸 和寿; 玉置 卓; 伊藤 大雄; 吉田 悠一
日本学術振興会, 科学研究費助成事業, 国立情報学研究所, 新学術領域研究(研究領域提案型), 情報理論・符号理論など離散数学における最先端の解析手法を使いこなし発展させることで, 計算限界解明の研究を進展させた. 具体的には(1) 劣線形時間計算における定数時間検査可能性の特徴付けや論理回路クラスの分離等, 種々のP対NP問題の類似の解決,(2) 3彩色問題に対する多項式時間近似アルゴリズムの世界記録更新等, グラフや制約充足問題に関する基本的な計算問題の計算複雑性の精微な解析,(3) (1)(2) の成果に基づいた, 劣線形時間計算やグラフアルゴリズムの機械学習や大規模データ処理等の分野への応用, が挙げられる., 24106003
研究期間 2012年06月28日 - 2017年03月31日 - データの巨大化から生じる不完全情報への対処に主眼をおいた近似計算
岩間 一雄; エイビス デイビッド; 宮崎 修一; 玉置 卓; 伊藤 大雄; 堀山 貴史; 吉田 悠一; 岡本 和也; 脊戸 和寿; 川原 純; 上野 賢哉
日本学術振興会, 科学研究費助成事業, 京都大学, 基盤研究(A), 不完全情報をいかに扱うかが現代アルゴリズムの大きな課題になっている． 本研究では「データの巨大化から生じる不完全情報に対処するための近似計算における，できるだけ一般性の高いアルゴリズム設計理論の体系化」を目的として研究を行った． 結果として，グラフ問題，アルゴリズム的ゲーム理論，乱化に関する基礎理論の様々な問題において，情報の不完全性を克服できるアルゴリズムの設計と解析に成功した．, 25240002
研究期間 2013年04月01日 - 2016年03月31日 - ゲーム解析の新パラダイム
伊藤 大雄
日本学術振興会, 科学研究費助成事業, 電気通信大学, 挑戦的萌芽研究, ゲーム・パズルに関する劣線形時間アルゴリズムを中心に、これまでに無い枠組みという視点から研究を推進し、以下の結果を得た。 (I) ケーキ分割問題に対し、劣線形時間アルゴリズムの枠組みを与え、具体的なアルゴリズムを提案した。(II) 一般化将棋問題に対し、定数時間アルゴリズムを提案した。(III) 川渡り問題に対し、「禁止状態」を入力とした問題を提案し、グラフのエキスパンダーを利用した新しい多項式時間アルゴリズムを提案した。(IV) n手からなる一般化ジャンケンについて、異なる手の間に引分けを考慮した問題に対し、引分けの総数の厳密な上下限を導くなどの諸性質を得た。, 24650006
研究期間 2012年04月01日 - 2016年03月31日 - ゲーム情報学：Ａｎｄ－Ｏｒ木の探索とゲーム・パズルの難しさの研究
岩田 茂樹; 武永 康彦; 笠井 琢美; 伊藤 大雄
日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(C), 本研究は、ゲーム情報学全般にわたる研究のうち、(1) And-Or 木のコンピュータによる探索、と (2) ゲームやパズルの複雑さに関する研究を行う、ことを目的とする。 And-Or 木（ゲーム木）のコンピュータによる探索では通常、評価関数が用いられる。ゲーム木の自然なモデルを定め、ゲーム木のある深さにおいて深さ優先探索により探索する局面数を考える。完全な評価関数に確率 p(0 - 空間的な情報補填を可能にするアルゴリズムの研究
岩間 一雄; エイビス デイビッド; 宮崎 修一; 玉置 卓; 伊藤 大雄; 加藤 直樹; 徳山 豪; 山下 雅史; 渡辺 治; 堀山 貴史; 川原 純; 森住 大樹; 伊藤 大雄
日本学術振興会, 科学研究費助成事業, 京都大学, 基盤研究(A), 不完全情報をいかに扱うかが現代アルゴリズムの大きな課題になっている.本研究では「空間的な情報の不完全性を克服できるアルゴリズムに関して,その設計技法と評価手法を含めた総合的体系を作り上げること」を目的として研究を行った.結果として,グラフ問題,アルゴリズム的ゲーム理論,乱化に関する基礎理論の様々な問題において,空間的な情報の不完全性を克服できるアルゴリズムの設計と解析に成功した., 22240001
研究期間 2010年 - 2012年 - 巨大情報からの超高速情報抽出アルゴリズムの研究
伊藤 大雄; 岩間 一雄
日本学術振興会, 科学研究費助成事業, 京都大学, 基盤研究(C), データが膨大である対象をあつかうための、高速アルゴリズムとその計算量の下界値に対して研究を行った。特に、対象となるデータのうちのごく一部、定数個しか見ないで問題を解くという定数時間アルゴリズムを中心に研究し、グラフの最大独立集合や最大マッチングのサイズの近似、外平面性の検査、疎性マトロイドのランクの近似、ナップザック問題の解の近似に対して、高速な定数時間アルゴリズムを与えた。また、線形下界値を示す技法をいくつか与えた。他に、ユニットディスクグラフを描画領域でパラメータ化し、いくつかの問題に対しFPTアルゴリズムと下界値を与えた。, 21500014
研究期間 2009年 - 2011年 - 情報補填を可能にするアルゴリズムの設計と解析
岩間 一雄; 加藤 直樹; 伊藤 大雄; 宮崎 修一; 玉置 卓; 杉原 厚吉; 徳山 豪; 山下 雅史; 渡辺 治; 堀山 貴史; 杉原 厚吉; 徳山 豪; 山下 雅史; 渡辺 治
日本学術振興会, 科学研究費助成事業, 京都大学, 基盤研究(A), 入力情報の不完全性をいかに克服する(情報を補填する)かが現代アルゴリズムの大きな課題となっている,本研究では,そのようなアルゴリズムが有すべき性質を厳密に議論し,具体的な設計技法と評価手法を含めた体系を作り上げることを目的として,研究を行った.結果として,オンライン,ネットワーク,マッチング,確率,幾何,分散等多岐にわたる分野で効率よいアルゴリズムの開発に成功した., 19200001
研究期間 2007年 - 2009年 - 巨大情報のアルゴリズム的超圧縮技術の研究
伊藤 大雄; 岩間 一雄; 中村 義作; 福田 宏; 福田 宏; 中村 義作
日本学術振興会, 科学研究費助成事業, 京都大学, 基盤研究(C), 指数爆発あるいは入力そのものが巨大である等の理由で従来困難とされてきた問題に対し、本来の目的を失うことなく視点を変えることによって効率的に解くことができる技法について研究した.特にグラフに「孤立」の概念を導入して部分グラフを列挙する問題、グラフの連結度に関する性質検査、家系図列挙問題などについて効率的なアルゴリズムを与えた.また、一部の問題については、そのアルゴリズムの効率が、ある意味で限界値であることも示した., 18500012
研究期間 2006年 - 2008年 - 新世代の計算限界-その解明と打破-
岩間 一雄; 伊藤 大雄; 加藤 直樹; 徳山 豪; 田中 圭介; 櫻井 幸一; 浅野 孝夫; 浅野 哲夫; 平田 富夫
日本学術振興会, 科学研究費助成事業, 京都大学, 特定領域研究, 近年のIT社会の大規模化と多様化によって, 従来は計算機があまり入り込まなかった分野においても, アルゴリズムが重要となってきている. また, 例えば配送計画問題をとっても, 配送コストのみではなく, 配送者の負荷の均質化や環境問題への配慮といった, 従来の評価尺度ではとらえきれない観点からの社会的要請があがっている. 本領域ではこうした状況に対処するため, 社会に役立つアルゴリズムをテーマに, 社会的評価基準のもとで数学的に保証されたアルゴリズムの開発・評価の体系化を目指している. 本領域の研究活動は平成19年度で終了した. すでに多くの研究成果が出されており, それらの多くは本領域の設定した目標を順調に達成するものである. 得られた成果をまとめ効果的に公表するため, 総括班のみ平成20年度も活動を行った. 具体的な活動は以下の通りである. (1) 成果報告書の作成 : 総括班および研究課題別の成果をまとめた報告書を作成した. 本特定で開催した研究集会の資料も, とりまとめて記載した. (2) 教科書の出版 : 本領域の分野の教科書を出版する(全16巻). 共立出版より6巻が刊行済みであり, 新たに1巻を刊行した. (3) ニュースレターの発行 : 本領域の最新情報を掲載したニュースレターを発行する. (4) ウェブサイト : 本領域の活動内容の広報として立ち上げた, ウェブサイト(http://keisan-genkai.lab2.kuis.kyoto-u.ac.jp/)の充実をはかった., 16092101
研究期間 2004年 - 2008年 - ネットワーク問題のモデル化とアルゴリズムの研究
伊藤 大雄; 岩間 一雄; 増澤 利光; 宮崎 修一; 堀山 貴史
日本学術振興会, 科学研究費助成事業, 京都大学, 特定領域研究, グラフは接続関係を表現する抽象モデルとして有用であり, 古くから盛んに研究されている数学的対象である. 本特定領域研究では, ネットワークや計算機上での問題をグラフ問題としてモデル化し, そのアルゴリズム開発の研究を行った. その結果、密な部分グラフ発見問題, 供給点配置問題, 頂点被覆問題, 巡回セールスマン問題, 自己安定化問題, 安定マッチング問題などの様々な実用的問題について, 効率的なアルゴリズムを得ることができた., 16092215
研究期間 2004年 - 2007年 - 工学的評価基準に基づく離散アルゴリズムの品質保証技術に関する研究
岩間 一雄; 伊藤 大雄; 宮崎 修一; 堀山 貴史
日本学術振興会, 科学研究費助成事業, 京都大学, 基盤研究(B), 離散アルゴリズムの評価基準は、漸近的な計算時間がほとんど唯一のものとされてきた。しかし、これは評価尺として適切でない場合もしばしば指摘され、様々な角度からアルゴリズムを評価する動きが高まってきた。たとえば、困難な組合せ問題を近似アルゴリズムで解く時の近似度や、将来の入力が分からないオンライン問題に対するアルゴリズムの良さをオフラインアルゴリズムの性能との比較で議論する競合比は、現在最も重要視されている尺度である。本研究では、このような新しい各種尺度を、「工学的評価基準」としてとらえ、そのもとで高性能なアルゴリズムを開発する。ネットワークアルゴリズム、マッチングアルゴリズム、SATアルゴリズムの観点から研究を進めた。以下、代表低な成果である安定結婚問題と頂点被覆問題について述べる。 安定結婚問題の拡張として、希望リストに同順位と不完全指定を許した問題においては最大サイズの安定マッチングを求める問題はNP困難であることが知られている。この問題では、2-近似アルゴリズムは自明である。これまで知られている最良の近似度は2-c/$\sqrt{n}$であったが、我々は初めて2よりも厳密によい近似度である1.8-近似アルゴリズムを達成した。 NP困難問題の一つである頂点被覆問題(VC)が2-ε近似可能か否かは極めて重要性の高い未解決問題であり、その近似不可能性が強く信じられている。我々は密なグラフ上のVCを考え、近似度2を大きく下回る2/(1+Δ/d)の近似アルゴリズムを開発した。ここで、Δはグラフの最大次数、dは平均次数を表す。もしもより良い近似率を達成する結果が存在するならば、一般のVCにおいて2-εの近似度が得られるため、我々の結果が最適である。, 16300002
研究期間 2004年 - 2006年 - インターネット問題のモデル化法と効率的算法の研究
伊藤 大雄; 岩間 一雄
日本学術振興会, 科学研究費助成事業, 京都大学, 基盤研究(C), 1.供給点配置問題:グラフG=(V,E)に対し、節点部分集合Sで、与えられたサイズp以下で、カバーする(Sとの間の連結度が所望の値kになっている)節点xの数(あるいは重み和)を最大にするようなSを求める問題を我々は提案し、最大被覆供給点配置問題と呼ぶ。本問題は、インターネット上でミラーサーバーを効率良く配置する問題が定式化されるため、応用上もたいへん重要な問題である。本年度は主にグラフが無向で、連結度が枝連結度である場合を対象とし、以下の結果を得た(ただしGの節点数をn、枝数をmとする)。(1)kが2以下である場合の0(np+m+nlogn)時間算法、(2)Gがk-1枝連結である場合の0(nm+n^2logn)時間算法、(3)Gの形状が木である場合の0(knp^2)時間算法。 2.孤立した密な部分グラフの列挙:グラフから密な部分グラフを見つけ出す問題は、インターネット検索アルゴリズムとの関係で近年注目を浴びている。しかしそのほとんどはNP困難、あるいは解が指数個存在するなど、非常に難しい問題と認識されている。しかし実用上必要なのは、その部分グラフが密であるだけでなく外部との連結が疎でもあるというということに我々は着目し、「孤立部分グラフ」という概念を提唱した。正の数cについて、k節点からなる部分グラフがc-孤立であるとは、外部への枝数がck未満であることを言う。我々は与えられたグラフから全ての極大c-孤立クリーク(クリーク=部分グラフで全節点間に枝があるもの)を列挙する0(c^52^{2c}m)時間アルゴリズムを得た。, 16500010
研究期間 2004年 - 2005年 - グラフ・ネットワーク・離散幾何学におけるアルゴリズムの研究
伊藤 大雄; 岩間 一雄
日本学術振興会, 科学研究費助成事業, 京都大学, 基盤研究(C), 1.供給点配置問題 供給点配置問題は、インターネットにおけるミラーサーバ配置問題に応用できる基本的問題である。本研究では、入力が有向グラフG=(V, E)で、両方向の流れに対応する制約条件λ(S, x)≧kとλ(x, S)≧hがあるような供給点配置問題に対し、kとhが定数である場合に多項式時間で動作するアルゴリズムを得た。 2.設備故障に強いインターネットルーチング方式 インターネットにおいて、設備故障などがおきた場合にネットワーク情報の変化を全網に通知して通信経路を変更するが、情報伝達の遅延の影響で、パケットがループに陥ってしまうという「ルーチングループ問題」がおきることが知られている。これを回避するために、ネットワークリソースの変化情報を段階的に流す手法を提案し、最適アルゴリズムを得た。また、リンク故障時の迂回方式として、各ノード毎に迂回テーブルを一つ用意するだけで、かつパケットのヘッダに1ビット加えるだけで実行できる方法を提案した。 3.ファイル転送木問題 与えられたグラフG=(V, E)の各節点x∈Vに対して出次数の上限値d(x)が与えられ、その制約の下での最短路木を求める問題に対し多項式時間アルゴリズムを得た。本問題は、通信ネットワークにおいてファイルを転送する際の適切な経路を計算する問題などに応用を持つ。さらに、出次数制限や最短路性などの制約を緩和した種々の問題について、多項式時間アルゴリズムを与えるか、さもなけれな計算困難であることを証明した。 4.ハイパーグラフの凸多角形上への描画 ハイパーグラフを平面上に描画した時の、各ハイパーエッジの作る面積の和と、凸3カットとの間に成立する、同値な関係を明らかにした。, 14580373
研究期間 2002年 - 2003年 - 工学的評価基準による離散アルゴリズムの高品質化に関する研究
岩間 一雄; 宮崎 修一; 伊藤 大雄; 岡部 寿男; 堀山 貴史
日本学術振興会, 科学研究費助成事業, 京都大学, 基盤研究(B), 離散アルゴリズムの良さの評価基準として、長期間に渡って、漸近的な計算時間がほとんど唯一のものとされてきた。しかし、この漸近的計算時間が評価尺度として適切でない場合が多いこともしばしば指摘され、様々な角度からアルゴリズムを評価する動きが高まってきた。たとえば、困難な組合せ問題を近似アルゴリズムで解く時の近似率や、将来の入力が分からないオンライン問題を解く時の競合比などである。我々は、このような新しい各種尺度を「工学的評価基準」としてとらえ、この視点のもとで高性能なアルゴリズムを開発する方法論について研究を行った。 結婚安定問題は多項式時間で解くことができると知られていたが、これを一般化し、希望リストに同順位を許した場合や希望リストを完全に指定しない場合にも多項式時間アルゴリズムを示した。同順位と不完全指定を同時に許した場合にはNP困難となるが、この場合に自明な近似率2を切る初めてのアルゴリズムを示した。 充足可能性問題では、局所探索系とバックトラック系の2つのアルゴリズムを相補的に組み合わせることにより、3-SATを1.324^n時間で解くアルゴリズムを構築した。また、与えられた論理式の充足可能性を保存したまま解の密度を濃縮した論理式を求める、論理式の濃縮問題に取り組んだ。 他に、オンラインアルゴリズム、ネットワークアルゴリズム、量子アルゴリズムの各テーマにおいて、アルゴリズムの高品質化に取り組んだ。, 13480081
研究期間 2001年 - 2003年 - グラフ・ネットワーク構造を持つ離散最適化問題の定式化とその効率的解法の研究
増山 繁; 巳波 弘佳; 市川 周一; 伊藤 大雄
日本学術振興会, 科学研究費助成事業, 豊橋技術科学大学, 特定領域研究(B), インターネット,マルチメディアネットワーク,移動体通信等の急激な普及にみられるような,近年における計算機や,情報通信技術の高度化に起因して新たに出現してきた問題の多くは,離散的構造を持つ.そこで,我々のグループでは,それらの問題に対して,グラフ・ネットワーク問題によるモデル化を行ない,その構造的な特徴を解明することによって,効率の良い解法を求めてきた. その結果,高度情報通信網,及び,その信頼性に関して,ある種のグラフ上のハミルトン閉路問題,2本の辺素な路問題,故障すると中継数が増大する端末を求める問題,また,高度情報通信網のモデル化とサーバーミラー配置,及び,移動体通信システムにおいて基地局への担当領域の割り当てに関連した問題等について成果を得た. また,未解決であったハムサンドイッチ定理の一般化等,離散幾何学,及び,一般化詰将棋問題等の離散構造を有するゲーム・パズルの計算複雑さに関して共に成果を得た.更に,離散最適化手法を用いた並列,ないし,分散負荷分散問題の解法,及び,専用計算回路の部分グラフ同型問題等の計算困難問題への適用についても実用上有用な成果を得た. 高度情報通信網上で提供されている大量の情報の活用を支援するための基礎技術として重要な情報検索,および,テキスト自動要約とその周辺の研究もTVニュース字幕生成のための要約,複数記事の要約,更には,要約に必要な換言知識の自動獲得,及び,それらのための基礎技術である構文解析等について成果を得た., 10205210
研究期間 1998年 - 2000年