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
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
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
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
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
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
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, 9711, 215-226, 2016, Peer-reviwed
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
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, 9943, 60-72, 2016, Peer-reviwed
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, 9943, 143-154, 2016, Peer-reviwed
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, 473-478, 2015, Peer-reviwed
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
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
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
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
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
International conference proceedings, English - Property Testing on k-Vertex-Connectivity of Graphs
Yuichi Yoshida; Hiro Ito
ALGORITHMICA, 62, 3-4, 701-712, Apr. 2012, Peer-reviwed
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
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
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
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, 7391, 7391, 498-509, 2012, Peer-reviwed
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
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, 41, 4, 1074-1093, 2012, Peer-reviwed
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), 407-413, 2012, Peer-reviwed
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, 27, 3, 321-326, May 2011, Peer-reviwed
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, 14, 89-93, 2011, Peer-reviwed
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, 7033, 27-+, 2011, Peer-reviwed
International conference proceedings, English - Complexity of the Stamp Folding Problem
Takuya Umesato; Toshiki Saitoh; Ryuhei Uehara; Hiro Ito
COMBINATORIAL OPTIMIZATION AND APPLICATIONS, 6831, 311-321, 2011, Peer-reviwed
International conference proceedings, English - Query-Number Preserving Reductions and Linear Lower Bounds for Testing
Yuichi Yoshida; Hiro Ito
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, E93D, 2, 233-240, Feb. 2010, Peer-reviwed
Scientific journal, English - TESTING k-EDGE-CONNECTIVITY OF DIGRAPHS
Yuichi Yoshida; Hiro Ito
JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY, 23, 1, 91-101, Feb. 2010, Peer-reviwed
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, 12, 120-127, 2010, Peer-reviwed
International conference proceedings, English - Testing Outerplanarity of Bounded Degree Graphs
Yuichi Yoshida; Hiro Ito
APPROXIMATION, RANDOMIZATION, AND COMBINATORIAL OPTIMIZATION: ALGORITHMS AND TECHNIQUES, 6302, 642-655, 2010, Peer-reviwed
International conference proceedings, English - Enumeration of Isolated Cliques and Pseudo-Cliques
Hiro Ito; Kazuo Iwama
ACM TRANSACTIONS ON ALGORITHMS, 5, 4, Article 40, Oct. 2009, Peer-reviwed
Scientific journal, English - Maximum-cover source location problems with objective edge-connectivity three
Kenya Sugihara; Hiro Ito
MATHEMATICAL METHODS OF OPERATIONS RESEARCH, 70, 1, 183-193, Aug. 2009, Peer-reviwed
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
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, 225-234, 2009, Peer-reviwed
International conference proceedings, English - Inferring pedigree graphs from genetic distances
Takeyuki Tamura; Hiro Ito
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, E91D, 2, 162-169, Feb. 2008, Peer-reviwed
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, 193-+, 2008, Peer-reviwed
International conference proceedings, English - Multi-commodity source location problems and price of greed
Hiro Ito; Mike Paterson; Kenya Sugihara
WALCOM: ALGORITHMS AND COMPUTATION, PROCEEDINGS, 4921, 169-+, 2008, Peer-reviwed
International conference proceedings, English - Property testing on k-vertex-connectivity of graphs
Yuichi Yoshida; Hiro Ito
AUTOMATA, LANGUAGES AND PROGRAMMING, PT 1, PROCEEDINGS, 5125, 539-550, 2008, Peer-reviwed
International conference proceedings, English - Transforming Graphs with the Same Degree Sequence
Sergey Bereg; Hiro Ito
COMPUTATIONAL GEOMETRY AND GRAPH THEORY, 4535, 25-+, 2008, Peer-reviwed
International conference proceedings, English - Multi-commodity source location problems and price of greed
Hiro Ito; Mike Paterson; Kenya Sugihara
WALCOM: ALGORITHMS AND COMPUTATION, PROCEEDINGS, 4921, 1, 169-+, 2008, Peer-reviwed
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, 23, 291-306, 2007, Peer-reviwed
Scientific journal, English - Semi-distance codes and Steiner systems
Hiro Ito; Midori Kobayashi; Gisaku Nakamura
GRAPHS AND COMBINATORICS, 23, 283-290, 2007, Peer-reviwed
Scientific journal, English - Impossibility of transformation of vertex labeled simple graphs preserving the cut-size order
Hiro Ito
Discrete Geometry, Combinatorics and Graph Theory, 4381, 59-69, 2007, Peer-reviwed
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, 4381, 1-+, 2007, Peer-reviwed
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, E89A, 5, 1370-1377, May 2006, Peer-reviwed
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, 333, 3, 347-353, Mar. 2005, Peer-reviwed
Scientific journal, English - Linear-time enumeration of isolated cliques
H Ito; K Iwama; T Osumi
ALGORITHMS - ESA 2005, 3669, 119-130, 2005, Peer-reviwed
Scientific journal, English - Three equivalent partial orders on graphs with real edge-weights drawn on a convex polygon
H Ito
DISCRETE AND COMPUTATIONAL GEOMETRY, 3742, 123-130, 2005, Peer-reviwed
Scientific journal, English - NA-edge-connectivity augmentation problems by adding edges
HH Miwa; H Ito
JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF JAPAN, 47, 4, 224-243, Dec. 2004, Peer-reviwed
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, E87A, 5, 1243-1250, May 2004, Peer-reviwed
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
International conference proceedings, English - Imperfectness of data for STS-based physical mapping
H Ito; K Iwama; T Tamura
EXPLORING NEW FRONTIERS OF THEORETICAL INFORMATICS, 155, 279-292, 2004, Peer-reviwed
International conference proceedings, English - Avoiding routing loops on the Internet
H Ito; K Iwama; Y Okabe; T Yoshihiro
THEORY OF COMPUTING SYSTEMS, 36, 6, 597-609, Nov. 2003, Peer-reviwed
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, 18, 4, 427-435, Aug. 2003, Peer-reviwed
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, 86, 4, 20-25, 2003, Peer-reviwed
Scientific journal, English - Sum of edge lengths of a multigraph drawn on a convex polygon
H Ito
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 24, 1, 41-47, Jan. 2003, Peer-reviwed
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, 40, 2, 63-70, Sep. 2002, Peer-reviwed
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, E85A, 5, 1026-1030, May 2002, Peer-reviwed
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
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, E85B, 1, 191-198, Jan. 2002, Peer-reviwed
Scientific journal, English - File transfer tree problems
H Ito; H Nagamochi; Y Sugiyama; M Fujita
ALGORITHMS AND COMPUTATION, PROCEEDINGS, 2518, 441-452, 2002, Peer-reviwed
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, 2866, 176-181, 2002, Peer-reviwed
Scientific journal, English - Minimum cost source location problem with vertex-connectivity requirements in digraphs
H Nagamochi; T Ishii; H Ito
INFORMATION PROCESSING LETTERS, 80, 6, 287-293, Dec. 2001, Peer-reviwed
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, 115, 1-3, 63-71, Nov. 2001, Peer-reviwed
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, E84A, 5, 1144-1151, May 2001, Peer-reviwed
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, 1969, 338-349, 2001, Peer-reviwed
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, 2098, 160-166, 2001, Peer-reviwed
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, E83A, 4, 704-712, Apr. 2000, Peer-reviwed
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, E83A, 4, 590-597, Apr. 2000, Peer-reviwed
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, E83A, 3, 492-496, Mar. 2000, Peer-reviwed
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, 222-226, 2000, Peer-reviwed
International conference proceedings, English - NP-completeness of stage illumination problems
H Ito; H Uehara; M Yokoyama
DISCRETE AND COMPUTATIONAL GEOMETRY, 1763, 158-165, 2000, Peer-reviwed
Scientific journal, English - 2-dimension ham sandwich theorem for partitioning into three convex pieces
H Ito; H Uehara; M Yokoyama
DISCRETE AND COMPUTATIONAL GEOMETRY, 1763, 129-157, 2000, Peer-reviwed
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, 66, 4, 209-213, May 1998, Peer-reviwed
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, E81A, 5, 832-841, May 1998, Peer-reviwed
Scientific journal, English - Edge connectivity between nodes and node-subsets
H Ito; M Yokoyama
NETWORKS, 31, 3, 157-163, May 1998, Peer-reviwed
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, 1533, 149-158, 1998, Peer-reviwed
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, E80A, 3, 534-543, Mar. 1997, Peer-reviwed
Scientific journal, English - Complexity and algorithm for reallocation problem
H Miwa; H Ito
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, E79A, 4, 461-468, Apr. 1996, Peer-reviwed
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, 78, 8, 52-62, Aug. 1995, Peer-reviwed
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, E78A, 3, 363-370, Mar. 1995, Peer-reviwed
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
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, 74, 12, 4025-4033, Dec. 1991, Peer-reviwed
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.
- 考える猫【フェロー記念招待講演】
伊藤大雄
Invited oral presentation, Japanese, 電子情報通信学会 コンピュテーション研究会, Invited
09 May 2024
- 09 May 2024 - 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
- 劣線形時間パラダイムの深化
伊藤 大雄
日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(C), 25K14987
Apr. 2025 - Mar. 2030 - 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
