Hiro ITO
| Department of Computer and Network Engineering | Professor |
| Cluster I (Informatics and Computer Engineering) | Professor |
Researcher Information
Field Of Study
Career
- 01 Apr. 2012
School of Informatics and Engineering, The University of Electro-Communications, Professor - 01 Jun. 2001 - 31 Mar. 2012
School of Informatics, Kyoto University, Associate Professor - 12 Jun. 2006 - 30 Sep. 2006
Department of Computer Science, The University of Warwick, Visiting Fellow (Academic Visitor) - 01 Apr. 1996 - 31 May 2001
Department of Information and Computer Science, Toyohashi University of Technology, Associate Professor - 01 Mar. 1995 - 31 Mar. 1996
NTT Laboratories, Senior Research Engineer - 01 Feb. 1990
NTT Laboratories, Research Engineer - 01 Apr. 1987
NTT Laboratories
Research Activity Information
Award
Paper
- Geodesic Paths Passing Through All Faces on A Polyhedron
Erik Demaine; Martin Demaine; David Eppstein; Hiro Ito; Yuta Katayama; Wataru Maruyama; Yushi Uno
Corresponding, The collection of selected paper of JCDCG^3 2022, LNCS, Springer, Dec. 2024, Peer-reviwed
In book, English - Numerically balanced dice on convex isohedra
Hiro Ito; Shunsuke Kanaya; Risa Tamechika
Corresponding, The collection of selected paper of JCDCG^3 2022, LNCS, Springer, Dec. 2024, Peer-reviwed
In book, English - 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
Corresponding, Thai Journal of Mathematics, 2023, Peer-reviwed
Scientific journal, English - 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, Aug. 2022, Peer-reviwed
International conference proceedings, English - Sublinear computation paradigm: constant-time algorithms and sublinear progressive algorithms
Kyohei Chiba; Hiro Ito
Corresponding, IEICE Transactions, 105-A, 3, Mar. 2022, Peer-reviwed
Scientific journal, English - 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, Jul. 2021, Peer-reviwed
International conference proceedings, English - Flat Folding a Strip with Parallel or Nonacute Zig-zag Creases with Mountain-Valley Assignment
Erik D. Demaine; Martin L. Demaine; Hiro Ito; Chie Nara; Izumi Shirahama; Tomohiro Tachi; Mizuho Tomura
Journal of Information Processing, 28, 12, 825-833, Dec. 2020, Peer-reviwed
Scientific journal, English - 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, Peer-reviwed
Scientific journal, English - Generalized shogi, chess, and xiangqui are constant-time testable
ITO Hiro; NAGAO Atsuki; PARK Teagun
IEICE Transactions, E102-A, 9, 1126-1133, Sep. 2019, Peer-reviwed
Scientific journal, English - Cookie Clicker
Erik D. Demaine; Hiro Ito; Stefan Langerman; Jayson Lynch; Mikhail Rudoy; Kai Xiao
Graphs and Combinatorics, 未定, 2019, Peer-reviwed
Scientific journal, English - 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, Peer-reviwed, Invited
Scientific journal, English - 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, Dec. 2018, Peer-reviwed
Scientific journal, English - 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, Peer-reviwed, 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.
International conference proceedings, English - 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, Peer-reviwed, 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.
Scientific journal, English - 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, 01 Aug. 2017, Peer-reviwed, 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.
Scientific journal, English - 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, 01 Aug. 2017, Peer-reviwed, 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.
Scientific journal, English - Transforming graphs with the same graphic sequence
Sergey Bereg; Hiro Ito
Journal of Information Processing, Information Processing Society of Japan, 25, 8, 627-633, 01 Aug. 2017, Peer-reviwed, 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.
Scientific journal, English - 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, 01 Jun. 2016, Peer-reviwed, 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.
International conference proceedings, English - 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, Peer-reviwed, 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.
International conference proceedings, English - 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, 01 Jan. 2016, Peer-reviwed, 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.
International conference proceedings, English - 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, Peer-reviwed
International conference proceedings, English - Constant-time algorithms for complex networks
Hiro ITO
Proceedings of the Asia-Pacific World Congress on Computer Science 2016 (APWConCS2016), to appear, 2016, Peer-reviwed
International conference proceedings, English - 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, Peer-reviwed, 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.
International conference proceedings, English - 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, Peer-reviwed, 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.
International conference proceedings, English - 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, Peer-reviwed, 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.
International conference proceedings, English - 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, Peer-reviwed, 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.
Scientific journal, English - 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, Peer-reviwed, 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
International conference proceedings, English - 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, Peer-reviwed, Invited
International conference proceedings, English - 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, Peer-reviwed
International conference proceedings, English - Testing outerplanarity of bounded degree graphs
YOSHIDA Yuichi; ITO Hiro
Algorithmica, to appear, 2014, Peer-reviwed
Scientific journal, English - Generalized River Crossing Problems
Hiro Ito; Stefan Langerman; Yuichi Yoshida
Theory of Computing Systems, Springer New York LLC, 56, 2, 418-435, 2014, Peer-reviwed, Invited, 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.
Scientific journal, English - 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, Dec. 2013, Peer-reviwed, 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.
Scientific journal, English - Helly Numbers of Polyominoes
Jean Cardinal; Hiro Ito; Matias Korman; Stefan Langerman
Graphs and Combinatorics, 29, 5, 1221-1234, Sep. 2013, Peer-reviwed, 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.
Scientific journal, English - 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, Peer-reviwed, 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.
International conference proceedings, English - Property Testing on k-Vertex-Connectivity of Graphs
Yuichi Yoshida; Hiro Ito
ALGORITHMICA, SPRINGER, 62, 3-4, 701-712, Apr. 2012, Peer-reviwed, 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.
Scientific journal, English - An almost optimal algorithm for Winkler's sorting pairs in bins
Hiro Ito; Junichi Teruyama; Yuichi Yoshida
Progress in Informatics, 9, 3-7, Mar. 2012, Peer-reviwed, 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.
Scientific journal, English - 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, Peer-reviwed, 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.
International conference proceedings, English - 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, Peer-reviwed, 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.
International conference proceedings, English - 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, Peer-reviwed, 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.
International conference proceedings, English - 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, Peer-reviwed, 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.
International conference proceedings, English - 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, Peer-reviwed, 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.
Scientific journal, English - Complexity of the stamp folding problem
UMESATO Takuya; SAITOH Toshiki; UEHARA Ryuhei; ITO Hiro; OKAMOTO Yoshio
Theoretical Computer Science, 497, 29, 13-19, 2012, Peer-reviwed
Scientific journal, English - 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, Peer-reviwed, 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.
International conference proceedings, English - Helly numbers of polyominoes
Jean CARDINAL; ITO Hiro; Matias KORMAN; Stefan LANGERMAN
The 23rd Canadian Conference on Computational Geometry (CCCG'11), 443--448, Aug. 2011, Peer-reviwed
International conference proceedings, English - 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, May 2011
Symposium, English - 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, May 2011, Peer-reviwed, 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.
Scientific journal, English - 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, Mar. 2011, Peer-reviwed
International conference proceedings, English - 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, Peer-reviwed, 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.
International conference proceedings, English - 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, Peer-reviwed, 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.
International conference proceedings, English - 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, Peer-reviwed, 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.
International conference proceedings, English - 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, Feb. 2010, Peer-reviwed, 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.
Scientific journal, English - TESTING k-EDGE-CONNECTIVITY OF DIGRAPHS
Yuichi Yoshida; Hiro Ito
JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY, SPRINGER, 23, 1, 91-101, Feb. 2010, Peer-reviwed, 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.
Scientific journal, English - 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, Peer-reviwed, 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.
International conference proceedings, English - 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, Peer-reviwed, 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)).
International conference proceedings, English - Enumeration of Isolated Cliques and Pseudo-Cliques
Hiro Ito; Kazuo Iwama
ACM TRANSACTIONS ON ALGORITHMS, ASSOC COMPUTING MACHINERY, 5, 4, Article 40, Oct. 2009, Peer-reviwed, 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.
Scientific journal, English - 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, Aug. 2009, Peer-reviwed, 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.
Scientific journal, English - The multi-commodity source location problems and the price of greed
Hiro Ito; Mike Paterson; Kenya Sugihara
Journal of Graph Algorithms and Applications, Brown University, 13, 1, 55-73, 2009, Given a graph G = (V, E), we say that a vertex subset S ⊆ V covers a vertex v ∈ 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 ∈ E if v and w are both covered. We propose the multi-commodity source location problem, which is such that given a vertex- and edge-weighted graph G, p players each select q vertices, and obtain a profit that is the total over all players of the weight of each player's 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 based on an ordered strategy, is tightly bounded by min{p, q}. Also when k = 2, we obtain tight bounds for vertex-unweighted trees when sources are located on the leaves.
Scientific journal, English - 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, Peer-reviwed, 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.
International conference proceedings, English - 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, Feb. 2008, Peer-reviwed, 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.
Scientific journal, English - 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, Peer-reviwed, 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.
International conference proceedings, English - 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, Peer-reviwed, 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.
International conference proceedings, English - 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, Peer-reviwed, 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.
International conference proceedings, English - Transforming Graphs with the Same Degree Sequence
Sergey Bereg; Hiro Ito
COMPUTATIONAL GEOMETRY AND GRAPH THEORY, SPRINGER-VERLAG BERLIN, 4535, 25-+, 2008, Peer-reviwed, 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.
International conference proceedings, English - 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, Peer-reviwed, 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.
International conference proceedings, English - 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, Sep. 2007, Peer-reviwed
International conference proceedings, English - Winning ways of weighted poset games
Hiro Ito; Gisaku Nakamura; Satoshi Takata
GRAPHS AND COMBINATORICS, SPRINGER TOKYO, 23, 291-306, 2007, Peer-reviwed, 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.
Scientific journal, English - Semi-distance codes and Steiner systems
Hiro Ito; Midori Kobayashi; Gisaku Nakamura
GRAPHS AND COMBINATORICS, SPRINGER TOKYO, 23, 283-290, 2007, Peer-reviwed, 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.
Scientific journal, English - 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, Peer-reviwed, 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.
International conference proceedings, English - 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, Peer-reviwed, 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'.
International conference proceedings, English - Maximum-Cover Source-Location Problem with Objective Edge-Connectivity Three
Kenya Sugihara; Hiro Ito
Electronic Notes in Discrete Mathematics, 25, 165-171, 01 Aug. 2006, Peer-reviwed
Scientific journal, English - Efficient methods for determining DNA probe orders
H. Ito; K. Iwama; T. Tamura
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E89A, 5, 1292-1298, May 2006, Peer-reviwed - 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, May 2006, Peer-reviwed, 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.
Scientific journal, English - Harary's generalized ticktacktoe
ITO Hiro
IEICE Transactions, J89-A, 6, 458--469, 2006, Peer-reviwed
Scientific journal, Japanese - Efficient methods of determining DNA probe sequences
ITO Hiro; IWAMA Kazuo; TAMURA Takeyuki
IEICE Transactions, E89-A, 5, 1292--1298, 2006, Peer-reviwed
Scientific journal, English - Two equivalent measures on weighted hypergraphs
ITO Hiro; NAGAMOCHI Hiroshi
Discrete Applied Mathematics, 154, 2330--2334, 2006, Peer-reviwed
Scientific journal, English - 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, Mar. 2005, Peer-reviwed, 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.
Scientific journal, English - Linear-time enumeration of isolated cliques
H Ito; K Iwama; T Osumi
ALGORITHMS - ESA 2005, SPRINGER-VERLAG BERLIN, 3669, 119-130, 2005, Peer-reviwed, 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.
Scientific journal, English - 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, Peer-reviwed, 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.
Scientific journal, English - 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, Dec. 2004, Peer-reviwed, 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.
Scientific journal, English - 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, May 2004, Peer-reviwed
International conference proceedings, English - 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, May 2004, Peer-reviwed, 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.
Scientific journal, English - Imperfectness of data for STS-based physical mapping
Hiro Ito; Kazuo Iwama; Takeyuki Tamura
IFIP Advances in Information and Communication Technology, Springer New York LLC, 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. © 2004 Springer Science + Business Media, Inc.
International conference proceedings, English - 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, Peer-reviwed, 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.
International conference proceedings, English - Avoiding routing loops on the Internet
H Ito; K Iwama; Y Okabe; T Yoshihiro
THEORY OF COMPUTING SYSTEMS, SPRINGER-VERLAG, 36, 6, 597-609, Nov. 2003, Peer-reviwed, 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.
Scientific journal, English - 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, Aug. 2003, Peer-reviwed, 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.
Scientific journal, English - Variable rate MPSK coded modulation using convolutional codes over modules
T Konishi; M Yokoyama; H Uehara; H Ito
ELECTRONICS AND COMMUNICATIONS IN JAPAN PART III-FUNDAMENTAL ELECTRONIC SCIENCE, SCRIPTA TECHNICA-JOHN WILEY & SONS, 86, 4, 20-25, 2003, Peer-reviwed, 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.
Scientific journal, English - 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, Jan. 2003, Peer-reviwed, 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.
Scientific journal, English - 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, Peer-reviwed
International conference proceedings, English - Can a hypergraph cover every convex polygon?
ITO Hiro; NAGAMOCHI Hiroshi
Proceedings of the 3rd Hungarian-Japanese Symposium 2003, 293--302, 2003, Peer-reviwed
International conference proceedings, English - 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, Sep. 2002, Peer-reviwed, 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.
Scientific journal, English - 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, May 2002, Peer-reviwed, 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.
Scientific journal, English - Packet relay control scheme based on priority regions in multihop wireless networks
KITAGISHI Yumiko; UEHARA Hideyuki; YAMAMOTO Akira; YOKOYAMA Mitsuo; ITO Hiro
IEICE Tansactions, The Institute of Electronics, Information and Communication Engineers, J85-B, 12, 2119--2128-456, 2002, Peer-reviwed
Scientific journal, Japanese - Safety information collecting network using self-organizing packet relay protocol
ODA Masato; UEHARA Hideyuki; YOKOYAMA Mitsuo; ITO Hiro
IEICE Tansactions, J85-B, 12, 2037--2044, 2002, Peer-reviwed
Scientific journal, Japanese - 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, Peer-reviwed, 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.
Scientific journal, English - 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, Jan. 2002, Peer-reviwed, 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.
Scientific journal, English - File transfer tree problems
H Ito; H Nagamochi; Y Sugiyama; M Fujita
ALGORITHMS AND COMPUTATION, PROCEEDINGS, SPRINGER-VERLAG BERLIN, 2518, 441-452, 2002, Peer-reviwed, 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.
Scientific journal, English - 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, Peer-reviwed
International conference proceedings, English - 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, Peer-reviwed, 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).
Scientific journal, English - 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, Dec. 2001, Peer-reviwed, 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.
Scientific journal, English - 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, Nov. 2001, Peer-reviwed, 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.
Scientific journal, English - 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, May 2001, Peer-reviwed, 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.
Scientific journal, English - 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, Apr. 2001, Peer-reviwed
International conference proceedings, English - 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, Apr. 2001, Peer-reviwed
International conference proceedings, English - 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, Peer-reviwed, 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).
Scientific journal, English - Convolutional codes over rings for Rayleigh fading channels
KONISHI Tatsumi; YOKOYAMA Mitsuo; UEHARA Hideyuki; ITO Hiro
IEICE Transactions, J84-A, 3, 834--839, 2001, Peer-reviwed
Scientific journal, Japanese - On PSPACE-completeness of generalized tsume-shogi with a given number of moves
YOKOTA Masaya; TSUKIJI Tatsuie; FUJII Shinji; ITO Hiro
IEICE Transactions, The Institute of Electronics, Information and Communication Engineers, J84-D-I, 1, 58--61-61, 2001, Peer-reviwed, 縦横Nますに王将を除く各駒がO(N)枚ずつ配置されている盤面が与えられたとき, 詰み手順があるかどうかを判定する問題を一般化つめ将棋問題と呼ぶ.伊藤らはその計算複雑さがNP困難であることを証明した.本論文では盤面とともに手数の上限を単進数で与えたときの一般化詰め将棋問題がPSPACE完全であることを証明する.
Scientific journal, Japanese - 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, Peer-reviwed, 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'.
Scientific journal, English - 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, Apr. 2000, Peer-reviwed, 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.
Scientific journal, English - 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, Apr. 2000, Peer-reviwed, 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.
Scientific journal, English - 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, Mar. 2000, Peer-reviwed, 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.
Scientific journal, English - 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, Peer-reviwed, 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.
International conference proceedings, English - NP-completeness of stage illumination problems
H Ito; H Uehara; M Yokoyama
DISCRETE AND COMPUTATIONAL GEOMETRY, SPRINGER-VERLAG BERLIN, 1763, 158-165, 2000, Peer-reviwed, 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.
Scientific journal, English - 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, Peer-reviwed, 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.
Scientific journal, English - 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, Mar. 1999, Peer-reviwed
International conference proceedings, English - 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, Oct. 1998, Peer-reviwed
International conference proceedings, English - 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, May 1998, Peer-reviwed, 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.
Scientific journal, English - 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, May 1998, Peer-reviwed, 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.
Scientific journal, English - Edge connectivity between nodes and node-subsets
H Ito; M Yokoyama
NETWORKS, JOHN WILEY & SONS INC, 31, 3, 157-163, May 1998, Peer-reviwed, 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.
Scientific journal, English - 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, Peer-reviwed, 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.
Scientific journal, English - 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, Mar. 1997, Peer-reviwed, 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.
Scientific journal, English - 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, Apr. 1996, Peer-reviwed, 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.
Scientific journal, English - 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, Aug. 1995, Peer-reviwed, 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.
Scientific journal, English - 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, Mar. 1995, Peer-reviwed, 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.)
Scientific journal, English - An algorithm using flow assignment for network performance estimation
MATSUZAKI Ryuichi; ITO Hiro
IEICE Transactions, J78-B-I, 3, 825--836, 1995, Peer-reviwed
Scientific journal, Japanese - Network topology construction method and its support system
Takashi Satake; Hiro Ito; Akiya Inoue
5th IEEE International Workshop on Computer-Aided Modeling, Analysis, and Design of Communication Links and Networks, CAMAD 1994, Institute of Electrical and Electronics Engineers Inc., 1994, This paper describes a network toplogy construction method for current and near-future telecommunication networks. The current telecommunication network is in a transitional period, and the wide range of telecommunication services and their usage patterns, as well as the appearance of new common carriers, is creating greater and more complex traffic variations. The introduction of dynamic routing, the transition to SDH-based transmission systems, switching-system renewal and upgrading, and network reconfiguration all necessitate various changes every day, and these changes cause changes in requirements for network design. The backbone network, that is, the basic network structure that provides connections between cities is determined based on long-term traffic prediction or strategic policy. In general, there are several switching units called nodes in a city. As the capacity of new switching systems and transmission systems increases, the number of network facilities, such as nodes and circuit-switched links, can be decreased. However, it will take a long time to renew all the facilities in a telecommunication network. SATAKE, ITO &
INOUE: Network Topology Construction Method and its support system-the area to which each node belongs. Constraints:-area-pairs should be connected,-the number of TGs between each area-pair. The final version of this paper will present how to define this problem as a directed graph problem, its features. However this problem seems intractable, the paper will present the algorithm to solve the problem optimally with linear time complexity. NETWORK TOPOLOGY ANALYSIS SUPPORT SYSTEM Network performance depends on not only the number of selectable two-link routes, but also the total number of trunks that can be used for call-connection between an origin-destination pair. The network topology analysis system is being developed to demonstrate and evaluate the constructed network. This system must support the following functions:-making network topology visible,-checking two-link routes,-evaluating network performance. These functions are used both for reconfiguring the whole network and for changing part of the network. Figure 3 shows a display example of this system.
International conference proceedings, English - Node-to-area connectivity of graphs
ITO Hiro
The Transactions of IEE of Japan, 114-C, 4, 463--469-469, 1994, Peer-reviwed
Scientific journal, Japanese - 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, May 1992, Peer-reviwed
International conference proceedings, English - An algorithm for defining a routing domain on dynamic routing
ITO Hiro; INOUE Akiya
IEICE Transactions, J75-B-I, 5, 323--332-332, 1992, Peer-reviwed
Scientific journal, Japanese - Multi-commodity flow problem with link number constraint
ITO Hiro
IEICE Transactions, J75-A, 3, 643--645, 1992, Peer-reviwed
Scientific journal, Japanese - 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, Dec. 1991, Peer-reviwed, 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.
Scientific journal, English
MISC
- ましゅの定数時間検査
兜石鼓太郎; 伊藤大雄
Last, Mar. 2024, 信学技報, COMP2023, 2024-03, 14-21, Summary national conference - ネコ教授が楽しむ数学・計算機科学講義
伊藤大雄
Lead, Jan. 2024, 数理解析研究所講究録, 2275, 12-17, Invited - 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------------------------------, 15 Aug. 2017, 情報処理学会論文誌, 58, 8, English, 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------------------------------, 15 Aug. 2017, 情報処理学会論文誌, 58, 8, English, 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., The Institute of Electronics, Information and Communication Engineers, 06 Nov. 2013, Mathematical Systems Science and its Applications : IEICE technical report, 113, 279, 113-119, English, 0913-5685, 110009886695, AA12529664 - Bumpy Pyramid Folding Problem
Zachary R.Abel; Erik D.Demaine; Martin L.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., Information Processing Society of Japan (IPSJ), 30 Oct. 2013, IPSJ SIG Notes, 2013, 19, 1-7, English, 0919-6072, 110009614899, AN1009593X - On A Generalization of River Crossing Problems
Hiro Ito; Stefan Langerman; Yuichi Yoshida
Apr. 2013, Proc. 6th Annual Meeting of Asian Association for Algorithms and Computation (AAAC), English, Peer-reviwed, Summary international conference - Testing graph rigidity in constant time
Hiro Ito; Shin-ichi Tanigawa; Yuichi Yoshida
Apr. 2011, Proc. 4th Annual Meeting of Asian Association for Algorithms and Computation (AAAC), English, Summary international conference - Constant-time approximation algorithms for the knapsack problem
ITO Hiro; KIYOSHIMA Susumu; YOSHIDA Yuichi
社団法人電子情報通信学会, Mar. 2011, IEICE technical report. Theoretical foundations of Computing, 110, 464, 29-36, Japanese, 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., The Institute of Electronics, Information and Communication Engineers, 18 Jan. 2010, IEICE technical report, 109, 391, 45-49, English, 0913-5685, 110008004172, AN10013152 - STOC2009 Report
ITO Hiro; YOSHIDA Yuichi
Information Processing Society of Japan (IPSJ), 15 Aug. 2009, IPSJ Magazine, 50, 8, 794-797, Japanese, 0447-8053, 110007339758 - Constant-time approximations using minimum value search for independent sets and matchings
Yuichi Yoshida; Masaki Yamamoto; Hiro Ito
Apr. 2009, Proc. 2nd Annual Meeting of Asian Association for Algorithms and Computation (AAAC), English, Summary international conference - DS-1-1 Improved Constant-Time Approximation Algorithms for Maximum Independent Sets and Maximum Matchings
Yoshida Yuichi; Yamamoto Masaki; Ito Hiro
The Institute of Electronics, Information and Communication Engineers, 04 Mar. 2009, Proceedings of the IEICE General Conference, 2009, 1, "S-21"-"S-22", Japanese, 110007094594 - Property Testing on k-Vertex-Connectivity of Graphs
YOSHIDA Yuichi; ITO Hiro
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 ε-far from k-vertex-connectivity when at least ε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 ε-far from k-vertex-connectivity with a probability of at least 2/3. The algorithm runs in O(d(c/(εd))^k log1/(εd)) time (c>1 is a constant) for given (k-1)-vertex-connected graphs, and, O(d((ck)/(εd))^klogk/(ε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., The Institute of Electronics, Information and Communication Engineers, 16 Jun. 2008, IEICE technical report, 108, 89, 49-55, English, 0913-5685, 110006951168, AN10013152 - On k-connectivity testing in degree-bounded graphs
Yuichi Yoshida; Hiro Ito
Apr. 2008, Proc. 1st Annual Meeting of Asian Association for Algorithms and Computation (AAAC), English, Summary international conference - Testing k-Edge-Connectivity of Digraphs
YOSHIDA Yuichi; ITO Hiro
社団法人電子情報通信学会, Jun. 2007, IEICE technical report. Theoretical foundations of Computing, 107, 127, 17-23, Japanese, 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., The Institute of Electronics, Information and Communication Engineers, 01 May 2006, IEICE transactions on fundamentals of electronics, communications and computer sciences, 89, 5, 1292-1298, English, 0916-8508, 110007502843, AA10826239 - On Transformation of Graphs with Preserving their Simpleness
ITO Hiro
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., Information Processing Society of Japan (IPSJ), 05 Nov. 2004, IPSJ SIG Notes, 2004, 109, 1-8, English, 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., The Institute of Electronics, Information and Communication Engineers, 01 May 2004, IEICE Trans. Fundamentals, A, 87, 5, 1243-1250, English, 0916-8508, 110003213026, AA10826239 - Subdividing hierarchy of classes of H - colorable graphs by circulant graphs
UEJIMA Akihiro; ITO Hiro
p-colorable graphs are - C7 - Coloring Problems of Planar Graphs
UEJIMA Akihiro; ITO Hiro
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^^^~ of a cycle of order ρ. This paper presents as follows: (1) classes of graphs which are ^^^~-coloring problem of planar graphs is NP-complete, and (3) there exists a class of graphs which are not 3-colorable but ^^^~-colorable., Information Processing Society of Japan (IPSJ), 19 Sep. 2002, IPSJ SIG Notes, 2002, 88, 67-74, Japanese, 0919-6072, 110002812525, AN1009593X - Relation among Edge Length of Convex Planar Drawings, Size of Linear Cuts, and Cross - Operations on Graphs
ITO Hiro
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 C ⪯G' for given G and G', where ⪯ is the partial order., Information Processing Society of Japan (IPSJ), 15 Mar. 2002, IPSJ SIG Notes, 2002, 29, 27-34, Japanese, 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., The Institute of Electronics, Information and Communication Engineers, 01 Mar. 2002, IEICE transactions on fundamentals of electronics, communications and computer sciences, 85, 3, 729-730, English, 0916-8508, 110003216806, AA10826239 - A Packet Relay Control Scheme based on Priority Regions in Multihop Wireless Networks
KITAGISHI Yumiko; UEHARA Hideyuki; YOKOYAMA Mitsuo; ITO Hiro
Flooding method is used to forward packets in multihop wireless networks. Conventional flooding causes a great increase of network traffic because all nodes which succeeded in receiving a packet forward it to their all neighbors. Heavy traffic leads to an increase of collision, which results in degradation of packet arrival ratio and throughput. In this paper, we propose a packet relay control scheme based on priority regions to reduce redundant forwarding packets. The simulation results show that proposed relay contorol scheme can reduce redundant packets relayed to the whole network without degradation of packet arrival ratio., The Institute of Electronics, Information and Communication Engineers, 04 Jan. 2002, Technical report of IEICE. DSP, 101, 539, 15-20, Japanese, 0913-5685, 110003280587, AN10060786 - A Packet Relay Control Scheme based on Priority Regions in Multihop Wireless Networks
KITAGISHI Yumiko; UEHARA Hideyuki; YOKOYAMA Mitsuo; ITO Hiro
Flooding method is used to forward packets in multihop wireless networks. Conventional flooding causes a great increase of network traffic because all nodes which succeeded in receiving a packet forward it to their all neighbors. Heavy traffic leads to an increase of collision, which results in degradation of packet arrival ratio and throughput. In this paper, we propose a packet relay control Scheme based on priority regions to reduce redundant forwarding packets. The simulation results show that proposed relay contorol scheme can reduce redundant packets relayed to the whole network without degradation of packet arrival ratio., The Institute of Electronics, Information and Communication Engineers, 04 Jan. 2002, Technical report of IEICE. RCS, 101, 545, 15-20, Japanese, 0913-5685, 110003305994, AN10060822 - A Packet Relay Control Scheme based on Priority Regions in Multihop Wireless Networks
KITAGISHI Yumiko; UEHARA Hideyuki; YOKOYAMA Mitsuo; ITO Hiro
Flooding method is used to forward packets in multihop wireless networks. Conventional flooding causes a great increase of network traffic because all nodes which succeeded in receiving a packet forward it to their all neighbors. Heavy traffic leads to an increase of collision, which results in degradation of packet arrival ratio and throughput. In this paper, we propose a packet relay control Scheme based on priority regions to reduce redundant forwarding packets. The simulation results show that proposed relay contorol scheme can reduce redundant packets relayed to the whole network without degradation of packet arrival ratio., The Institute of Electronics, Information and Communication Engineers, 03 Jan. 2002, Technical report of IEICE. SAT, 101, 542, 15-20, Japanese, 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., The Institute of Electronics, Information and Communication Engineers, 25 Apr. 2000, The Institute of Electronics, Information and Communication Engineers Transactions on Fundamentals of Electronics, Communications and Computer Sciences, A, 83, 4, 704-712, English, 0916-8508, 110003208579, AA10826239 - Computational complexity of a generalized Tsume-Shogi
ITO Hiro; FUJII Shinji; UEHARA Hideyuki; YOKOYAMA Mitsuo
Computational complexity of a generalized Tsume-Shogi, which uses a board of n×n and O(n) pieces except for Gyoku (king) and one Gyoku, is investigated. It is shown that a generalized Tsume-Shogi is NP-hard even if no Hisha (Rook), no Kaku (Bishop), and no nari-koma (raised piece) are used and Gyoku is checkmated at the center of the boar d that is the initial place of Gyoku., The Institute of Electronics, Information and Communication Engineers, 21 Jul. 1999, IEICE technical report. Theoretical foundations of Computing, 99, 194, 17-24, Japanese, 0913-5685, 110003191783, AN10013152 - A Study of Adaptive Permission Probability Control Scheme for Slotted ALOHA System with Near-Far Effect
MORIYAMA Takayuki; UEHARA Hideyuki; YOKOYAMA Mitsuo; ITO Hiro
Throughput performance of slotted ALOHA system is degraded as increasing the number of simultaneous users so called channel load. To improve the throughput performance, several access control methods were proposed. However, this improvement of throughtput is not always shared equally by all of the terminals. Considering the near-far effect, the throughtput of terminals located far from the base station is much smaller than that of terminals located near the base station. Therefore, this paper presents a new access control scheme considering near-far effect in slotted ALOHA system. As a result, it is found that the throughput performance of the terminals located far from base station is the same as that of the terminals near the base station., The Institute of Electronics, Information and Communication Engineers, 20 Aug. 1998, Technical report of IEICE. SSE, 98, 240, 73-78, Japanese, 0913-5685, 110003235127, AN10060742 - A Study of Adaptive Permission Probability Control Scheme for Slotted ALOHA System with Near-Far Effect
MORIYAMA Takayuki; UEHARA Hideyuki; YOKOYAMA Mitsuo; ITO Hiro
Throughput performance of slotted ALOHA system is degraded as increasing the number of simultaneous users so called channel load. To improve the throughput performance, several access control methods were proposed. However, this improvement of throughtput is not always shared equally by all of the terminals. Considering the near-far effect, the throughtput of terminals located far from the base station is much smaller than that of terminals located near the base station. Therefore, this paper presents a new access control scheme considering near-far effect in slotted ALOHA system. As a result, it is found that the throughput performance of the terminals located far from base station is the same as that of the terminals near the base station., The Institute of Electronics, Information and Communication Engineers, 23 Apr. 1998, Technical report of IEICE. RCS, 98, 20, 73-78, Japanese, 110003305076, AN10060822 - Minimum size flow-sink-set location problem with various node flow-demands
ITO Hiro; YOKOYAMA Mitsuo
For a given graph G=(V, E), edge capacities c(e) for edges e∈E and flow-demands v∈V for nodes d(v), a problem for finding the minimum size T⊆V such that the maximum flow-amount between v and T is greater than or equal to d(v) for every v∈V is called Minimum size flow-sink-set location problem (FSSL). 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) and s(n, m) is the time required to solve the maximum flow problem of a graph with nodes and m edges., The Institute of Electronics, Information and Communication Engineers, 30 May 1997, IEICE technical report. Theoretical foundations of Computing, 97, 83, 41-48, English, 110003191267, AN10013152 - An O (m+np3.5) time algorithm for determining a given graph is (n - p) -node- connected
ITO Hiro; YOKOYAMA Mitsuo
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., Information Processing Society of Japan (IPSJ), 17 Oct. 1996, IPSJ SIG Notes, 1996, 100, 57-64, Japanese, 0919-6072, 110002812266, AN1009593X - A Dimensioning Algorithm using a Heuristic Flow Assignment Method for Networks with Dynamic Routing
Satake Takashi; Ito Hiro; Inoue Akiya
This paper proposes a new dimensioning algorithm for telecommunication networks with dynamic routing.This algorithm uses a multi-hour engineering method and it assigns traffic flow heuristically.It is characterized by flexibility with respect to changes in network conditions,such as network structure and the constraints on network elements,and by high-speed calculation.The dimensioning algorithm is described,and numerical examples on an eight-node network with two time-period traffic matrices show that the algorithm reduces cost while maintaining a given grade-of- service., The Institute of Electronics, Information and Communication Engineers, 22 Oct. 1993, IEICE technical report. Information networks, 93, 291, 43-50, Japanese, 110003196095, AN10013072 - Evaluation of circuit-switched network performance estimation using flow assignment
Matsuzaki Ryuichi; Ito Hiro
For design and management of circuit-switched networks controlled with dynamic routing,it is important to compute traffic flow over each trunk group.A fast computation method using heuristic flow assignment is proposed,considering that actual networks are large-scaled and complex-structured.The proposed method has the characteristics:it is applicable to the model that cannot be formulated strictly,and not much dependent on network configuration or scale.And this method is shown to be effective through numerical calculation., The Institute of Electronics, Information and Communication Engineers, 01 Oct. 1993, Technical report of IEICE. SSE, 93, 257, 135-140, Japanese, 0913-5685, 110003235016, AN10060742 - Evaluation of Flow-Assignment Algorithms on Telecommunication Networks with STR.
松崎隆一; 伊藤大雄; 井上明也
1993, 電子情報通信学会大会講演論文集, 1993, Shunki Pt 3, 1349-1369, 200902120344424150 - A Dimensioning Method for Networks with Dynamic Routing, STR.
佐竹孝; 伊藤大雄; 井上明也
1993, 電子情報通信学会大会講演論文集, 1993, Shuki Pt 3, 1349-1369, 200902145349858002 - Isolated-control Call-level Routing Function in a Dynamic Routing, STR and its Performance Evaluation.
井上明也; 伊藤大雄
1992, NTT R & D, 41, 6, 0915-2326, 200902016074400480 - Effect of Hybrid Control on Dynamic Routing.
伊藤大雄; 井上明也
1992, 電子情報通信学会大会講演論文集, 1992, Shunki Pt 3, 1349-1369, 200902058704730586 - An effective heuristic algorithm on a routing domain definition for dynamic routing.
伊藤大雄; 井上明也
1991, 電子情報通信学会全国大会講演論文集, 1991, Spring Pt 3, 200902064613874488 - Robustness Evaluation on Prediction Error of Routing-Domain Definition Algorithms for STR.
伊藤大雄; 井上明也
1991, 電子情報通信学会大会講演論文集, 1991, Shuki Pt 3, 1349-1369, 200902068983630516 - A routing domain definition algorithm for dynamic routing in telecommunications networks.
伊藤大雄; 井上明也
1990, 電子情報通信学会技術研究報告, 89, 418(IN89 113-121), 0913-5685, 200902002701244782 - Algorithms for constructing set of alternate routes in telecommunication networks.
伊藤大雄; 井上明也
1990, 電子情報通信学会全国大会講演論文集, 1990, Spring Pt.3, 200902064111600449
Books and other publications
- イラストで学ぶ離散数学
伊藤大雄
Textbook, Japanese, Single work, 講談社, 07 Sep. 2019, 9784065170014 - データ構造とアルゴリズム（コンピュータサイエンス教科書シリーズ ２）
伊藤大雄
Textbook, Japanese, Single work, コロナ社, 28 Sep. 2017, 9784339027020 - ビッグデータ・マネジメント --- データサイエンティストのためのデータ利活用技術と事例
嶋田茂; 伊藤大雄
General book, Japanese, Joint work, 第１編 第１章 第１節 ビッグデータの高速処理に向けた超高速アルゴリズムと計算理論, （株）エヌ・ティー・エス, 10 Mar. 2014, 9784864690843 - 離散数学のすすめ
伊藤大雄; 宇野裕之; 伊藤大雄; 名 著
General book, Japanese, Editor, 編集 および まえがき プロローグ「離散数学へのいざない」 第４章「最短路問題」 第７章「ケーキ分割問題」 第９章「フランク・ハラリィの一般化三並べ」 エピローグ「論文のできるまで --- 一般化ハムサンドイッチ定理を題材にして」 あとがき, 現代数学社, May 2010 - パズル・ゲームで楽しむ数学 --- 娯楽数学の世界
伊藤大雄
Japanese, Single work, 森北出版, Feb. 2010 - 離散幾何学における未解決問題集
秋山仁; 伊藤大雄; 訳
Japanese, Joint translation, 第３章「相似コピーによる詰め込みと被覆」, シュプリンガー・ジャパン, 2009 - アルゴリズム工学 --- 計算困難問題への挑戦
杉原厚吉; 茨木俊秀; 浅野孝夫; 山下雅史; 伊藤大雄
Japanese, Joint work, 4.10節 「２次元ハムサンドイッチ定理の一般化」, 共立出版, Jun. 2001 - ネットワーク設計理論（岩波講座「インターネット」第５巻）
滝根哲哉; 伊藤大雄; 西尾章治郎
Japanese, Joint work, 第４章「グラフ・ネットワークアルゴリズムの基本知識」 第５章「ネットワーク構成問題」, 岩波書店, Jun. 2001
Lectures, oral presentations, etc.
- Sublinear-Time Paradigm --- How to Challenge Big Data
Hiro Ito
Keynote oral presentation, English, The 13th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2019), Invited, International conference
13 Dec. 2019 - Generalized shogi and chess are constant-time tastable
Hiro Ito
Invited oral presentation, English, The 12th International Symposium on Operations Research & Its Applications (ISORA 2015), Invited, International conference
Aug. 2015 - Transformation of Graphs and their Simpleness
Hiro Ito
Invited oral presentation, English, he Japan Conference on Discrete and Computational Geometry 2004, Invited, International conference
Oct. 2004
Affiliated academic society
Research Themes
- Development of the sublinear-time paradigm
伊藤 大雄
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, The University of Electro-Communications, Grant-in-Aid for Scientific Research (C), 本研究では研究代表者の提案している「劣線形時間パラダイム」を広く展開するための理論研究を行っている。２０２１年度の主な成果は以下の通りである。 (I) 漸進型アルゴリズム(progressive algorithm)の結果をまとめた論文が論文誌に採録・出版された。「漸進型アルゴリズム」とは、データを徐々に読み込みながら段々と精度の高い解を求めていく手法であり、研究代表者によって提案されたものである。我々はこれまでに、「定数時間アルゴリズム」と「全てのデータを読み込む線形以上の計算時間のアルゴリズム」の両者が存在する任意の問題に対し、オーダの意味での各々の計算時間を悪化させることなく、両者を円滑に繋げる漸進型アルゴリズムが構築できることを証明した。これは片側誤り、両側誤りどちらにも適用可能であり、また本技法はグラフに限らず、どのような対象、モデルに対しても適用可能であると考えられ、非常に一般性のある結果である。(II) 機器をスリープ状態にしておくことで再起動の際の時間やエネルギー消費量の節減を図る制御は広く行われている。しかしスリープ状態は少しだが電力を消費し続けるので、長く保つと逆に損になる。この問題はオンライン問題の一種の「スキーレンタル問題」という形で定式化され、その競合比（小さいほど良く、１が最適）は２でこれ以上改善出来ないことが既存研究によって証明され、それが常識とされてきた。しかしその競合比２を与えるアルゴリズムは、最悪に備える為に多くの場合で明らかに無駄と考えられる動作をせざるを得なかった。そこで担当者は、競合比を2+ε（∀ε>0）と僅かに緩和することで、多くの実用的な場合にほぼ無駄が無い様に制御する方法を考案した。その結果を論文誌に投稿し採録・出版された。, 20K11671
01 Apr. 2020 - 31 Mar. 2023 - 効率的な最大および極大クリーク抽出アルゴリズムの開発と応用
富田 悦次; 若月 光夫; 西野 哲朗; 伊藤 大雄
日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(C), 最大クリーク厳密解抽出の分枝限定アルゴリズムに対するこれまでの研究により，最大クリークの近似解が非常に有効に活用出来ることを明らかにしてきている．その近似精度が良くなれば分枝限定はより有効に働く．しかし，近似解抽出のために時間を要すると，総実行時間としては必ずしも短縮とはならず，近似精度と時間との兼ね合いが重要となる．そこで先ず，最大クリーク近似解の抽出を一層高速化し，その上で精度を向上させることにより，総合的に最大クリーク厳密解抽出を効率化した． 続いて，分枝限定のために近似彩色だけでなくMaxSATも用いることにより分枝限定がより強力化されることをこれまでに確認してきたが，MaxSATあるいはその簡略形実行のためのオーバーヘッドの大きさが最大クリーク厳密解抽出総実行時間短縮の妨げとなっていた．これに対しては，MaxSATの簡略形と従来提唱してきていた再番号付け（再彩色）との類似性に着目して両者を融合させることにより，これまでよりも少ないオーバーヘッドによって，有効な分枝限定効果を発揮出来るようにした．さらに，分枝限定アルゴリズムの内部動作は入力グラフの特徴に応じて効率が左右されるため，出来る限り効率がより発揮されるようにと内部動作を適応的に切り替えるようにした． 以上を総合することにより，最大クリーク厳密解抽出のための従来の分枝限定アルゴリズムを有意に高速化することに成功した． このような最大クリーク厳密解抽出アルゴリズムは，容易に最大クリーク全列挙アルゴリズムへと拡張出来る．これにより，符号理論における最良な多元単一削除訂正符号の構成に関しての新たな知見を得ることが出来た． 極大クリーク全列挙問題についてもさらに理論的，実験的に検討を続け，有効な進展結果を得た．, 17K00006
01 Apr. 2017 - 31 Mar. 2022 - Sublinear-Time Paradigm
Ito Hiro
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, The University of Electro-Communications, Grant-in-Aid for Challenging Exploratory Research, The object of this project is establishing fundamental techniques for the “Sublinear-Time Paradigm.” The most remarkable result in this project is presenting a universal algorithm to complex networks, e.g., web graphs and social networks. That is, we define a class of (infinite) multigraphs, named HSF (Hierarchical Scale Free), which models a kind of hierarchical complex networks and prove that every property is constant-time testable for HSF. This is the first nontrivial universal constant-time algorithm on a graph class of sparse and degree-unbounded graphs, what is called the general graphs., 15K11985
01 Apr. 2015 - 31 Mar. 2019 - Much faster algorithms for finding maximum and maximal cliques and their applications
TOMITA Etsuji
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, The University of Electro-Communications, Grant-in-Aid for Scientific Research (C), We have developed much faster algorithms for finding a maximum clique. These have been accomplished by introducing a near-maximum clique finding algorithm and by applying appropriately sorting and coloring vertices to the underlying branch-and-bound algorithm for finding a maximum clique. The effectiveness of the above algorithms has been confirmed by extensive computational experiments. In addition, we have also given a weaker condition under that the maximum clique problem can be solved in polynomial time in theory. Our previous algorithm for enumerating maximal cliques has been extended to have algorithms for enumerating maximal pseudo-cliques. They are confirmed to work effectively for the analysis of networks., 25330009
01 Apr. 2013 - 31 Mar. 2018 - Studies on Limits of Computation via Information and Coding Theory
Kawarabayashi Kenichi
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, National Institute of Informatics, Grant-in-Aid for Scientific Research on Innovative Areas (Research in a proposed research area), We make progress in the study on limits of computation by exploiting and developing state of the art techniques in discrete mathematics such as information and coding theory. More concretely, we obtain the following results: (1) resolution of various analogous problems to the P vs. NP problem, including a characterization of constant time testability of properties in sub-linear time computation and separations of Boolean circuit classes, (2) fine-grained complexity analysis of fundamental computational problems concerning graphs and constraint satisfaction problems, including a world record polynomial time approximation algorithm for the 3 coloring problem, and (3) Applications of sub-linear time computation and graph algorithms to the areas such as machine learning and big data processing, based on the results of (1)(2)., 24106003
28 Jun. 2012 - 31 Mar. 2017 - Approximate Computing to Cope with Imperfect Information from Growing Data Size
IWAMA KAZUO; AVIS David; MIYAZAKI Shuichi; TAMAKI Suguru; ITO Hiro; HORIYAMA Takashi; YOSHIDA Yuichi; OKAMOTO Kazuya; SETO Kazuhisa; KAWAHARA JUN
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, Kyoto University, Grant-in-Aid for Scientific Research (A), One of the main challenge in modern algorithm design is to cope with insufficient information. In this study, we try to construct a general framework for design of approximation algorithms that can cope with insufficient information due to rapidly growing data size. As a result, we give design and analysis of such algorithms for various problems in several fields such as graph problems, algorithmic game theory and randomized computation theory., 25240002
01 Apr. 2013 - 31 Mar. 2016 - A new paradigm of game analyses
Ito Hiro
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, The University of Electro-Communications, Grant-in-Aid for Challenging Exploratory Research, We considered new frameworks on algorithms mainly on puzzles and games, and have obtained the following results: (I) For the cake-cutting problem, we presented a framework on sublinear-time algorithms and gave some algorithms in the framework. (II) For the generalized shogi problem, we presented a constant-time algorithm, i.e., we showed that it is constant-time solvable. (III) For river crossing problems, we presented a new formulation that requires prohibited states for inputs and gave a polynomial-time algorithms by using expanders. (IV) For generalized shogi with n signs, we considered jankens in which draws between different signs are allowed, and found some properties, e.g., tight upper and lower bounds of the number of draws., 24650006
01 Apr. 2012 - 31 Mar. 2016 - Game informatics: Search of And-Or tree and Computational Complexity of games and puzzles
IWATA Shigeki; TAKENAGA Yasuhoko; KASAI Takumi; ITO Hiroo
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, The University of Electro-Communications, Grant-in-Aid for Scientific Research (C), This research is concerned with Game Informatics. The themes are (1) computer search of And-Or trees, and (2) computational complexity of games and puzzles. Search of And-Or tree (game-tree) by computers generally use evaluation function. We define our game-tree model, and compare numbers of configurations to be searched by depth-first search at the designated depth of our game-tree under various evaluation functions. Our result shows that the number of configurations when an evaluation function is applied, which is as close as the perfect evaluation function with probability p (0 - Studies on Algorithms for Insufficient Spatial Information
IWAMA Kazuo; AVIS David; MIYAZAKI Shuichi; TAMAKI Suguru; ITO Hiro; KATOH Naoki; TOKUYAMA Takeshi; YAMASHITA Masafumi; WATANABE Osamu; HORIYAMA Takashi; KAWAHARA Jun; MORIZUMI Hiroki
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, Kyoto University, Grant-in-Aid for Scientific Research (A), One of the main challenge in modern algorithm design is to copewith insufficient information. In this study, we try to construct a general framework fordesign and evaluation of algorithms that can cope with insufficient spatial information. Asa result, we give design and analysis of such algorithms for various problems in severalfields such as graph problems, algorithmic game theory and randomized computationtheory., 22240001
2010 - 2012 - Hypervelocity information extraction from huge informations
ITO Hiro; IWAMA Kazuo
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, Kyoto University, Grant-in-Aid for Scientific Research (C), We investigated fast algorithms for treating big data, and lower bounds about them. Especially, algorithms that see only constant number of data of the given instance are mainly investigated. We obtained fast constant-time algorithms for approximating the size of the maximum independent set and the maximum matching of graphs, a testing outerplanarity of graphs, approximating the rank of sparsity matroids, and approximating the solution of the knapsack problem. And we presented new tools for showing linear lower bounds for testing algorithms. Moreover, we considered to parametrize unit disk graphs by the area, and gave some FPT algorithms and lower bounds on some problems on them., 21500014
2009 - 2011 - Design and Analysis of Algorithms for Insufficient Information
IWAMA Kazuo; KATOH Naoki; ITO Hiro; MIYAZAKI Shuichi; TAMAKI Suguru; SUGIHARA Kokichi; TOKUYAMA Takeshi; YAMASHITA Masafumi; WATANABE Osamu; HORIYAMA Takashi
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, Kyoto University, Grant-in-Aid for Scientific Research (A), One of the main challenge in modern algorithm design is to cope with insufficient information (to complement information). In this study, we rigorously discuss the desirable property of such algorithms and try to construct a framework for it including design techniques and evaluation method. As a result, we obtain efficient algorithms in various fields such as online, network, matching, randomized, geometric and distributed algorithms., 19200001
2007 - 2009 - Research on techniques for algorithmic super-compression of huge data
ITO Hiro; IWAMA Kazuo; NAKAMURA Gisaku; FUKUDA Hiroshi
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, Kyoto University, Grant-in-Aid for Scientific Research (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 - Research on modeling and algorithms for network problems
ITO Hiro; IWAMA Kazuo; MASUZAWA Toshimitsu; MIYAZAKI Shuichi; HORIYAMA Takashi
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, Kyoto University, Grant-in-Aid for Scientific Research on Priority Areas, グラフは接続関係を表現する抽象モデルとして有用であり, 古くから盛んに研究されている数学的対象である. 本特定領域研究では, ネットワークや計算機上での問題をグラフ問題としてモデル化し, そのアルゴリズム開発の研究を行った. その結果、密な部分グラフ発見問題, 供給点配置問題, 頂点被覆問題, 巡回セールスマン問題, 自己安定化問題, 安定マッチング問題などの様々な実用的問題について, 効率的なアルゴリズムを得ることができた., 16092215
2004 - 2007 - Studies on Diarete Algorithms with Guaranteed Quality based on Engineering Criteria
IWAMA Kazuo; ITO Hiro; MIYAZAKI Shuichi; HORIYAMA Takashi
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, Kyoto University, Grant-in-Aid for Scientific Research (B), Traditionally the quality of discrete algorithms has been evaluated mostly by their asymptotic running time. However, it is often pointed out that running time is not a suitable measure of quality for some applications. Recently various measures have been proposed to evaluate algorithms in many perspectives. For example, "approximation ratio" is used to evaluate approximation algorithms, where an approximation algorithm must efficiently compute reasonable solutions for hard combinatorial problems. Another example, "competitive ratio" is used to evaluate online algorithms, where in online computation an algorithm must decide how to act on incoming items of information without any knowledge of future inputs. Both measures play very important roles in current algorithm theory. In our research, we think these new measures for algorithms as "quality for engineering" and develop high performance algorithms with respect to this quality. We mainly study network algorithms, matching algorithms and satisfiability algorithms. The followings are representative results of our project. There is an extension of stable matching problems, where ties and incomplete lists are allowed in preference lists. Finding maximum stable matchings in this setting is known to be NP-hard and (trivial) 2-approximation algorithm is also known. We show a 1.8-approximating algorithm for the problem, which first achieves the approximation ratio below 2 and improves the previous best ratio of 2-c/$\sqrt{n}$. It is an important open question whether minimum vertex cover problems (VC) are approximable within 2-ε and it is widely believed that the answer is in the negative. We consider VC on dense graphs and show a 2 /(1+A/d) approximation algorithm, which greatly improves the ratio 2 for general graphs. Here A, (d) is a maximum (average, resp.) degree of an input graph. The result is tight in the sense that if an improvement is possible, then we would have 2-approximation algorithms for general graphs., 16300002
2004 - 2006 - Research on Modeling of the Internet Problems and Efficient Algorithms
ITO Hiro; IWAMA Kazuo
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, Kyoto University, Grant-in-Aid for Scientific Research (C), 1. Maximum-Cover Source Location Problems For a given graph G=(V,E) with n vertices and m edges and positive integers k and p, the maximum-cover source location problem is a problem of finding a vertex subsets (sources) S consisting of at most p vertices maximizing the number of covered vertices by S, where a vertex v is called "covered by S" if the edge-connectivity between S and v is at least k. This problem has applications of locating mirror servers on the Internet. For this problem we obtain the following results : (1) an O(np+m+nlogn) time algorithm for k at most 2, (2) an O(nm+n^2 logn) time algorithm for G of k-1 edge connected, (3) an O(knp^2) time algorithm for G of trees. 2. Enumerating Isolated Cliques Problem of finding dense subgraphs from a graph has a close relation to the Internet search problems and recently attracts considerable attention. However, almost such problems are hard, e.g., NP-hard even for approximation. We pay attention to that for such applications we should find subgraphs not only dense inside but also sparse between outside, and we introduce an idea of "isolation," i.e., a subgraph S with k vertices is c-isolated if there exists less than ck edges S and the outside of S, where c is called an "isolation factor." We presented an O(c^5 2^{2c}m) time algorithm for enumerating all c-isolated subgraphs from a given graph with n vertices and m edges. From this, we directly obtain that we can enumerate all c-isolated graphs in lenear time if c is a constant, and polynomial time if c=O(logn). We also show that these bounds are tight., 16500010
2004 - 2005 - Algorithms on Graphs, Networks, and Discrete Geomerty
ITO Hiroo; IWAMA Kazuo
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, KYOTO UNIVERSITY, Grant-in-Aid for Scientific Research (C), 1.Source Location Problems For a source location problem on digraphs and with constraints of edge-connectivity of both directions, we gave a polynomial-time algorithm. 2.Fault-tolerant Routing Method of the Internet For avoiding the "routing loop problem," which occurs when a network condition have been changed, we proposed a routing method to broadcast the information of the change gradually. We proved that this method avoids routing loops at all, and moreover we find the minimum number of steps of the broadcasting. 3.File Transfer Tree Problem For a given digraph, a specified vertex (root), and an upper bound of out-degree for each vertex, we consider a problem of finding a shortest path tree rooted on the root satisfying the out-degree constraint. We presented a polynomial time algorithm for this problem. 4.Properties of Hypergraphs Drawn on a Convex Polygon We consider hypergraph drawing on a convex polygon and found equivalence between a condition on the sum of areas of hyperedges and a condition on convex three-cuts of the hypergraph., 14580373
2002 - 2003 - High Quality Discrete Algorithms Based on Engineering Criteria
IWAMA Kazuo; MIYAZAKI Shuichi; ITO Hiro; OKABE Yasuo; HORIYAMA Takashi
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, Kyoto University, Grant-in-Aid for Scientific Research (B), Discrete algorithms have been evaluated by the unique measure 'asymptotic time complexity' for many cases. Recently, however, many other measures have been proposed, e.g., the approximation ratios for solving combinatorial problems approximately, and the competitive ratios for solving online problems in which we have no information on the future inputs. In this research, we studied these new measures as the criteria based on engineering requirements, and developed the methodologies for qualifying algorithms from this point of view. As to the stable marriage problems, it is known to be solvable in polynomial time. We have generalized the problem, and proved that it is also solvable in polynomial time even when ties in the lists or incomplete lists are allowed. While we proved the intractability for the case both ties and incompleteness are allowed, we proposed an approximation algorithm that achieves an approximation ratio less than 2. As to the satisfiability problems, we developed a 1.324^n algorithm for 3-SAT by complementarily combining two types of algorithms based on, the local search and the backtracking. We also considered condensing the density (i.e., the ratio of satisfying assignments to the 2^n assignments) of formulas. Other research topics are as follows ; online algorithms, network algorithms, quantum algorithms., 13480081
2001 - 2003 - Discrete Optimization Problems with Graph and Network Structures and Their Efficient Solution Methods
MASUYAMA Shigeru; MIWA Hiroyoshi; ICHIKAWA Shuichi; ITO Hiro
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, Toyohashi University of Technology, Grant-in-Aid for Scientific Research on Priority Areas (B), A number of problems which have emerged due to the recent rapid progress of Internet, multimedia networks, mobile and wireless networks and computer technology have a discrete structure in nature. Thus we first formalize some of such problems as graph and/or network problems and tried to obtain efficient solution methods by elucidating their structural feature. As a result, efficient algorithms, either parallel or sequential, for Hamiltonian circuit problem on an in-tournament graph, two edge-disjoint paths problem on tournament graph, hinge vertex problem in an interval graph and a trapezoid graph were obtained in the field of network reliability. Moreover, some results on location problems of servers and mirrors on multimedia networks and area assignment to base stations in mobile and wireless networks are also obtained. In discrete geometry, generalization of the 2-dimension ham sandwich problem which was an open problem was solved and NP-completeness of stage illumination problem was also clarified. On discrete games and puzzles, NP-hardness of rotation type cell-mazes and PSPACE-completeness of generarized Tsume-Shogi with a given number of moves were proved. Hardware accelerator for subgraph isomorphism problem was developed and static load balancing of parallel PDE solver for distributed computing environment is also investigated. As technologies for supporting users to utilize a large amount of information now available via Internet, etc, some results on automatic text summarization, a retrieval method for relevant documents and knowledge-acquisition from corpus were also obtained., 10205210
1998 - 2000
