博士（工学）, 京都大学

Recreational Mathematics

Discrete Mathematics

Discrete Algorithms

娯楽数学

離散数学

離散アルゴリズム

情報通信, 情報学基礎論, 理論計算機科学

自然科学一般, 幾何学, 離散幾何学

2012年04月01日
電気通信大学 大学院 情報理工学研究科, 教授

2001年06月01日 - 2012年03月31日
京都大学 大学院 情報学研究科, 助教授(2007.3.31まで)～准教授

2006年06月12日 - 2006年09月30日
Department of Computer Science, The University of Warwick, 客員研究員

1996年04月01日 - 2001年05月31日
豊橋技術科学大学 情報工学系, 講師

1995年03月01日 - 1996年03月31日
日本電信電話株式会社 通信網研究所, 主任研究員

1990年02月01日
日本電信電話株式会社 通信網総合研究所, 研究主任

1987年04月01日
日本電信電話株式会社 基礎研究所

1985年04月 - 1987年03月
京都大学, 工学研究科, 数理工学専攻

1981年04月 - 1985年03月
京都大学, 工学部, 数理工学科, 日本国

受賞日 2022年03月
電子情報通信学会
先進的グラフアルゴリズムと離散幾何学と娯楽数学の研究
フェロー（電子情報通信学会）
その他の賞

Geodesic Paths Passing Through All Faces on A Polyhedron
Erik Demaine; Martin Demaine; David Eppstein; Hiro Ito; Yuta Katayama; Wataru Maruyama; Yushi Uno
責任著者, The collection of selected paper of JCDCG^3 2022, LNCS, Springer, 出版日 2024年12月, 査読付
論文集(書籍)内論文, 英語

Numerically balanced dice on convex isohedra
Hiro Ito; Shunsuke Kanaya; Risa Tamechika
責任著者, The collection of selected paper of JCDCG^3 2022, LNCS, Springer, 出版日 2024年12月, 査読付
論文集(書籍)内論文, 英語

Multifold tiles of polyominoes and convex lattice polygons
Kota Chida; Erik D. Demaine; Martin L. Demaine; David Eppstein; Adam Hesterberg; Takashi Horiyama; John Iacono; Hiro Ito; Stefan Langerman; Ryuhei Uehara; Yushi Uno
責任著者, Thai Journal of Mathematics, 出版日 2023年, 査読付
研究論文（学術雑誌）, 英語

Computational complexity of flattening fixed-angle orthogonal chains
Erik D. Demaine; Hiro Ito; Jayson Lynch; Ryuhei Uehara
Proceedings of The 34th Canadian Conference on Computational Geometry, online巻, 掲載ページ 1-7, 出版日 2022年08月, 査読付
研究論文（国際会議プロシーディングス）, 英語

Sublinear computation paradigm: constant-time algorithms and sublinear progressive algorithms
Kyohei Chiba; Hiro Ito
責任著者, IEICE Transactions, 105-A巻, 3号, 出版日 2022年03月, 査読付
研究論文（学術雑誌）, 英語

Decrease and reset for power‐down
James Andro-Vasko; Wolfgang Bein; Hiro Ito; Shoji Kasahara; Jun Kawahara
Energy Systems, Springer, Springer Science and Business Media LLC, published online巻, 出版日 2021年09月03日, 査読付
研究論文（学術雑誌）, 英語

Turning Around and Around: Motion Planning through Thick and Thin Turnstiles
Aster Greenblatt; Oscar Hernandez; Robert A. Hearn; Yichao Hou; Hiro Ito; Minwoo Joshua Kang; Aaron Williams; Andrew Winslow
Proceedings of The 33rd Canadian Conference on Computational Geometry (CCCG2021), published online巻, 掲載ページ 377-387, 出版日 2021年07月, 査読付
研究論文（国際会議プロシーディングス）, 英語

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, 出版日 2020年12月, 査読付
研究論文（学術雑誌）, 英語

K_3 edge cover problem in a wide sense
Kyohei Chiba; Remy Belmonte; Hiro Ito; Michael Lampis; Atsuki Nagao; Yota Otachi
Journal of Information Processing, 28巻, 12号, 掲載ページ 849-859, 出版日 2020年12月, 査読付
研究論文（学術雑誌）, 英語

Twenty Years of Progress of $$\hbox {JCDCG}^3$$
Jin Akiyama; Hiro Ito; Toshinori Sakai; Yushi Uno
Graphs and Combinatorics, Springer Science and Business Media LLC, 36巻, 2号, 掲載ページ 181-203, 出版日 2020年03月
研究論文（学術雑誌）

On the characterization of 1-sided error strongly-testable graph properties for bounded-degree graphs
Hiro Ito; Areej Khoury; Ilan Newman
Journal of Computational Complexity, Springer, 29巻, Article 1号, 掲載ページ 1-45, 出版日 2020年, 査読付
研究論文（学術雑誌）, 英語

Generalized shogi, chess, and xiangqui are constant-time testable
ITO Hiro; NAGAO Atsuki; PARK Teagun
IEICE Transactions, E102-A巻, 9号, 掲載ページ 1126-1133, 出版日 2019年09月, 査読付
研究論文（学術雑誌）, 英語

Modulation-Adaptive Link-Disjoint Path Selection Model for 1+1 Protected Elastic Optical Networks
Yuto Kishi; Nattapong Kitsuwan; Hiro Ito; Bijoy Chand; Chatterjee; Eiji Oki
IEEE Access, 7巻, 1号, 掲載ページ 25422-25437, 出版日 2019年02月, 査読付
研究論文（学術雑誌）, 英語

Preface for the Special Issue on the Project "Foundation of Innovative Algorithms for Big Data".
Naoki Katoh; Yuya Higashikawa; Hiro Ito; Shun Kataoka; Takuya Kida; Toshiki Saitoh; Tetsuo Shibuya; Kazuyuki Tanaka; Yushi Uno
Rev. Socionetwork Strateg., 13巻, 2号, 掲載ページ 99-100, 出版日 2019年
研究論文（学術雑誌）

Cookie Clicker
Erik D. Demaine; Hiro Ito; Stefan Langerman; Jayson Lynch; Mikhail Rudoy; Kai Xiao
Graphs and Combinatorics, 未定巻, 出版日 2019年, 査読付
研究論文（学術雑誌）, 英語

What graph properties are constant-time testable? --- dense graphs, sparse graphs, and complex networks
ITO Hiro
The Review of Socionetwork Strategies, Springer, 13巻, 2号, 掲載ページ 101-121, 出版日 2019年, 査読付, 招待
研究論文（学術雑誌）, 英語

Hyperfiniteness of real-world newtorks
Yutaro Honda; Yoshitake Inoue; Hiro Ito; Munehiro Sasajima; Junichi Teruyama; Yushi Uno
The Review of Socionetwork Strategies, Springer, 13巻, 2号, 掲載ページ 123-141, 出版日 2019年, 査読付, 招待
研究論文（学術雑誌）, 英語

Energy efficiency and renewable energy management with multi-state power-down system
James Andro-Vasko; Wolfgang Bein; Hiro Ito
Information, 10巻, 2号, 掲載ページ 44:1-44:21, 出版日 2018年12月, 査読付
研究論文（学術雑誌）, 英語

A heuristic for state power down systems with few states
James Andro-Vasko; Wolfgang Bein; Hiro Ito; Govind Pathak
Advances in Intelligent Systems and Computing, Springer Verlag, 558巻, 掲載ページ 877-882, 出版日 2018年, 査読付
研究論文（国際会議プロシーディングス）, 英語

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年, 査読付
研究論文（学術雑誌）, 英語

A much faster algorithm for finding a maximum clique with computational experiments
Etsuji Tomita; Sora Matsuzaki; Atsuki Nagao; Hiro Ito; Mitsuo Wakatsuki
Journal of Information Processing, Information Processing Society of Japan, 25巻, 8号, 掲載ページ 667-677, 出版日 2017年08月01日, 査読付
研究論文（学術雑誌）, 英語

Unfolding and dissection of multiple cubes, tetrahedra, and doubly covered squares
Zachary Abel; Brad Ballinger; Erik D. Demaine; Martin L. Demaine; Jeff Erickson; Adam Hesterberg; Hiro Ito; Irina Kostitsyna; Jayson Lynch; Ryuhei Uehara
Journal of Information Processing, Information Processing Society of Japan, 25巻, 8号, 掲載ページ 610-615, 出版日 2017年08月01日, 査読付
研究論文（学術雑誌）, 英語

Transforming graphs with the same graphic sequence
Sergey Bereg; Hiro Ito
Journal of Information Processing, Information Processing Society of Japan, 25巻, 8号, 掲載ページ 627-633, 出版日 2017年08月01日, 査読付
研究論文（学術雑誌）, 英語

How to solve the cake-cutting problem in sublinear time
Hiro Ito; Takahiro Ueda
Leibniz International Proceedings in Informatics, LIPIcs, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 49巻, 出版日 2016年06月01日, 査読付
研究論文（国際会議プロシーディングス）, 英語

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年, 査読付
研究論文（国際会議プロシーディングス）, 英語

Folding a paper strip to minimize thickness
Erik D. Demaine; David Eppstein; Adam Hesterberg; Hiro Ito; Anna Lubiw; Ryuhei Uehara; Yushi Uno
Journal of Discrete Algorithms, Elsevier, 36巻, 掲載ページ 18-26, 出版日 2016年01月01日, 査読付
研究論文（国際会議プロシーディングス）, 英語

Every property is testable on a natural class of scale-free multigraphs
Hiro ITO
Proceedings of the 24th European Symposium of Algorithms (ESA 2016), LIPICS, 57巻, 掲載ページ 51:1-51:12, 出版日 2016年, 査読付
研究論文（国際会議プロシーディングス）, 英語

Constant-time algorithms for complex networks
Hiro ITO
Proceedings of the Asia-Pacific World Congress on Computer Science 2016 (APWConCS2016), to appear巻, 出版日 2016年, 査読付
研究論文（国際会議プロシーディングス）, 英語

Single-Player and Two-Player Buttons & Scissors Games
Kyle Burke; Erik D. Demaine; Harrison Gregg; Robert A. Hearn; Adam Hesterberg; Michael Hoffmann; Hiro Ito; Irina Kostitsyna; Jody Leonard; Maarten Loeffler; Aaron Santiago; Christiane Schmidt; Ryuhei Uehara; Yushi Uno; Aaron Williams
DISCRETE AND COMPUTATIONAL GEOMETRY AND GRAPHS, JCDCGG 2015, 9943巻, 掲載ページ 60-72, 出版日 2016年, 査読付
研究論文（国際会議プロシーディングス）, 英語

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年, 査読付
研究論文（国際会議プロシーディングス）, 英語

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年, 査読付
研究論文（国際会議プロシーディングス）, 英語

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年, 査読付
研究論文（学術雑誌）, 英語

Folding a Paper Strip to Minimizing Thickness
Erik D. DEMAINE; David EPPSTEIN; Adam HESTERBERG; Hiro ITO; Anna LUBIW; Ryuhei UEHARA; Yushi UNO
Proceeding of Workshop on Algorithms and Computation 2015 (WALCOM 2015), Springer, 8973巻, 掲載ページ 113-124, 出版日 2015年, 査読付, In this paper, we study how to fold a specified origami crease pattern in order to minimize the impact of paper thickness. Specifically, origami designs are often expressed by a mountain-valley pattern (plane graph of creases with relative fold orientations), but in general this specification is consistent with exponentially many possible folded states. We analyze the complexity of finding the best consistent folded state according to two metrics: minimizing the total number of layers in the folded state (so that a "flat folding" is indeed close to flat), and minimizing the total amount of paper required to execute the folding (where "thicker" creases consume more paper). We prove both problems strongly NPcomplete even for 1D folding. On the other hand, we prove both problems fixed-parameter tractable in 1D with respect to the number of layers.WALCOM: Algorithms and Computation, 9th International Workshop, WALCOM 2015, Dhaka, Bangladesh, February 26-28, 2015. Proceedings
研究論文（国際会議プロシーディングス）, 英語

Generalized shogi and chess are constant-time tastable
Hiro ITO; Atsuki NAGAO; Teagun PARK
Proceedings of the 12th International Symposium on Operations Research & Its Applications (ISORA 2015), IET Digital Library, 掲載ページ 1-6, 出版日 2015年, 査読付, 招待
研究論文（国際会議プロシーディングス）, 英語

Computational complexity of inverse word search problem
Hiro ITO; Shinnosuke SEKI
Proceedings of the 12th International Symposium on Operations Research & Its Applications (ISORA 2015), IET Digital Library, 掲載ページ 41-44, 出版日 2015年, 査読付
研究論文（国際会議プロシーディングス）, 英語

Bumpy Pyramid Folding.
Zachary Abel,Erik D. Demaine; Martin L. Demaine; Hiro Ito; Jack Snoeyink; Ryuhei Uehara
Proceedings of the 26th Canadian Conference on Computational Geometry, CCCG 2014, Halifax, Nova Scotia, Canada, 2014, Carleton University, Ottawa, Canada, 出版日 2014年, 査読付

Testing outerplanarity of bounded degree graphs
YOSHIDA Yuichi; ITO Hiro
Algorithmica, to appear巻, 出版日 2014年, 査読付
研究論文（学術雑誌）, 英語

Generalized River Crossing Problems
Hiro Ito; Stefan Langerman; Yuichi Yoshida
Theory of Computing Systems, Springer New York LLC, 56巻, 2号, 掲載ページ 418-435, 出版日 2014年, 査読付, 招待
研究論文（学術雑誌）, 英語

On computational complexity of graph inference from counting
Szilárd Zsolt Fazekas; Hiro Ito; Yasushi Okuno; Shinnosuke Seki; Kei Taneishi
Natural Computing, 12巻, 4号, 掲載ページ 589-603, 出版日 2013年12月, 査読付
研究論文（学術雑誌）, 英語

Helly Numbers of Polyominoes
Jean Cardinal; Hiro Ito; Matias Korman; Stefan Langerman
Graphs and Combinatorics, 29巻, 5号, 掲載ページ 1221-1234, 出版日 2013年09月, 査読付
研究論文（学術雑誌）, 英語

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年, 査読付
研究論文（国際会議プロシーディングス）, 英語

Property Testing on k-Vertex-Connectivity of Graphs
Yuichi Yoshida; Hiro Ito
ALGORITHMICA, 62巻, 3-4号, 掲載ページ 701-712, 出版日 2012年04月, 査読付
研究論文（学術雑誌）, 英語

An almost optimal algorithm for Winkler's sorting pairs in bins
Hiro Ito; Junichi Teruyama; Yuichi Yoshida
Progress in Informatics, 9号, 掲載ページ 3-7, 出版日 2012年03月, 査読付
研究論文（学術雑誌）, 英語

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年, 査読付
研究論文（国際会議プロシーディングス）, 英語

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年, 査読付
研究論文（国際会議プロシーディングス）, 英語

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年, 査読付
研究論文（国際会議プロシーディングス）, 英語

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年, 査読付
研究論文（国際会議プロシーディングス）, 英語

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年, 査読付
研究論文（学術雑誌）, 英語

Complexity of the stamp folding problem
UMESATO Takuya; SAITOH Toshiki; UEHARA Ryuhei; ITO Hiro; OKAMOTO Yoshio
Theoretical Computer Science, 497巻, 29号, 掲載ページ 13-19, 出版日 2012年, 査読付
研究論文（学術雑誌）, 英語

Constant-Time Approximation Algorithms for the Optimum Branching Problem on Sparse Graphs
Mitsuru Kusumoto; Yuichi Yoshida; Hiro Ito
2012 THIRD INTERNATIONAL CONFERENCE ON NETWORKING AND COMPUTING (ICNC 2012), 掲載ページ 407-413, 出版日 2012年, 査読付
研究論文（国際会議プロシーディングス）, 英語

Helly numbers of polyominoes
Jean CARDINAL; ITO Hiro; Matias KORMAN; Stefan LANGERMAN
The 23rd Canadian Conference on Computational Geometry (CCCG'11), 掲載ページ 443--448, 出版日 2011年08月, 査読付
研究論文（国際会議プロシーディングス）, 英語

Testing Algorithms for (k, l)-Sparsity and (k, l)-Edge-Connected Orientability
Hiro Ito; Shin-ichi Tanigawa; Yuichi Yoshida
Proc. 7th Hungarian-Japanese Symposium on Discrete Math, 掲載ページ 447-456, 出版日 2011年05月
研究論文（研究会，シンポジウム資料等）, 英語

Arrangements of n Points whose Incident-Line-Numbers are at most n/2
Jin Akiyama; Hiro Ito; Midori Kobayashi; Gisaku Nakamura
GRAPHS AND COMBINATORICS, 27巻, 3号, 掲載ページ 321-326, 出版日 2011年05月, 査読付
研究論文（学術雑誌）, 英語

Cannibal animal games: a new variant of tic-tac-toe
Jean CARDINAL; Sebastien COLETTE; ITO Hiro; Matias KORMAN; Stefan LANGERMAN; SAKIDANI Hikaru; Perouz TASLAKIAN
The 27th European Workshop on Computational Geometry (EuroCG 2011), 掲載ページ 131--134, 出版日 2011年03月, 査読付
研究論文（国際会議プロシーディングス）, 英語

PSPACE-completeness of the Weighted Poset Game
Hiro Ito; Satoshi Takata
OPERATIONS RESEARCH AND ITS APPLICATIONS: IN ENGINEERING, TECHNOLOGY AND MANAGEMENT, 14巻, 掲載ページ 89-93, 出版日 2011年, 査読付
研究論文（国際会議プロシーディングス）, 英語

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年, 査読付
研究論文（国際会議プロシーディングス）, 英語

Complexity of the Stamp Folding Problem
Takuya Umesato; Toshiki Saitoh; Ryuhei Uehara; Hiro Ito
COMBINATORIAL OPTIMIZATION AND APPLICATIONS, 6831巻, 掲載ページ 311-321, 出版日 2011年, 査読付
研究論文（国際会議プロシーディングス）, 英語

Query-Number Preserving Reductions and Linear Lower Bounds for Testing
Yuichi Yoshida; Hiro Ito
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, E93D巻, 2号, 掲載ページ 233-240, 出版日 2010年02月, 査読付
研究論文（学術雑誌）, 英語

TESTING k-EDGE-CONNECTIVITY OF DIGRAPHS
Yuichi Yoshida; Hiro Ito
JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY, 23巻, 1号, 掲載ページ 91-101, 出版日 2010年02月, 査読付
研究論文（学術雑誌）, 英語

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年, 査読付
研究論文（国際会議プロシーディングス）, 英語

Testing Outerplanarity of Bounded Degree Graphs
Yuichi Yoshida; Hiro Ito
APPROXIMATION, RANDOMIZATION, AND COMBINATORIAL OPTIMIZATION: ALGORITHMS AND TECHNIQUES, 6302巻, 掲載ページ 642-655, 出版日 2010年, 査読付
研究論文（国際会議プロシーディングス）, 英語

Enumeration of Isolated Cliques and Pseudo-Cliques
Hiro Ito; Kazuo Iwama
ACM TRANSACTIONS ON ALGORITHMS, 5巻, 4号, 掲載ページ Article 40, 出版日 2009年10月, 査読付
研究論文（学術雑誌）, 英語

Maximum-cover source location problems with objective edge-connectivity three
Kenya Sugihara; Hiro Ito
MATHEMATICAL METHODS OF OPERATIONS RESEARCH, 70巻, 1号, 掲載ページ 183-193, 出版日 2009年08月, 査読付
研究論文（学術雑誌）, 英語

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年
研究論文（学術雑誌）, 英語

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年, 査読付
研究論文（国際会議プロシーディングス）, 英語

Inferring pedigree graphs from genetic distances
Takeyuki Tamura; Hiro Ito
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, E91D巻, 2号, 掲載ページ 162-169, 出版日 2008年02月, 査読付
研究論文（学術雑誌）, 英語

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年, 査読付
研究論文（国際会議プロシーディングス）, 英語

Multi-commodity source location problems and price of greed
Hiro Ito; Mike Paterson; Kenya Sugihara
WALCOM: ALGORITHMS AND COMPUTATION, PROCEEDINGS, 4921巻, 掲載ページ 169-+, 出版日 2008年, 査読付
研究論文（国際会議プロシーディングス）, 英語

Property testing on k-vertex-connectivity of graphs
Yuichi Yoshida; Hiro Ito
AUTOMATA, LANGUAGES AND PROGRAMMING, PT 1, PROCEEDINGS, 5125巻, 掲載ページ 539-550, 出版日 2008年, 査読付
研究論文（国際会議プロシーディングス）, 英語

Transforming Graphs with the Same Degree Sequence
Sergey Bereg; Hiro Ito
COMPUTATIONAL GEOMETRY AND GRAPH THEORY, 4535巻, 掲載ページ 25-+, 出版日 2008年, 査読付
研究論文（国際会議プロシーディングス）, 英語

Multi-commodity source location problems and price of greed
Hiro Ito; Mike Paterson; Kenya Sugihara
WALCOM: ALGORITHMS AND COMPUTATION, PROCEEDINGS, 4921巻, 1号, 掲載ページ 169-+, 出版日 2008年, 査読付
研究論文（国際会議プロシーディングス）, 英語

Snaky is a winner with one handicap
ITO Hiro; MIYAGAWA Hiromitsu
8th Hellenic European Conference on Computer Mathematics and its Applications (HERCMA 2007), 掲載ページ 25--26, 出版日 2007年09月, 査読付
研究論文（国際会議プロシーディングス）, 英語

Winning ways of weighted poset games
Hiro Ito; Gisaku Nakamura; Satoshi Takata
GRAPHS AND COMBINATORICS, 23巻, 掲載ページ 291-306, 出版日 2007年, 査読付
研究論文（学術雑誌）, 英語

Semi-distance codes and Steiner systems
Hiro Ito; Midori Kobayashi; Gisaku Nakamura
GRAPHS AND COMBINATORICS, 23巻, 掲載ページ 283-290, 出版日 2007年, 査読付
研究論文（学術雑誌）, 英語

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年, 査読付
研究論文（国際会議プロシーディングス）, 英語

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年, 査読付
研究論文（国際会議プロシーディングス）, 英語

Maximum-Cover Source-Location Problem with Objective Edge-Connectivity Three
Kenya Sugihara; Hiro Ito
Electronic Notes in Discrete Mathematics, 25巻, 掲載ページ 165-171, 出版日 2006年08月01日, 査読付
研究論文（学術雑誌）, 英語

Efficient methods for determining DNA probe orders
Ito Hiro; Iwama Kazuo; Takeyuki Tamura
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, E89A巻, 5号, 掲載ページ 1292-1298, 出版日 2006年05月, 査読付

Maximum-cover source-location problems
Kenya Sugihara; Hiro Ito
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, E89A巻, 5号, 掲載ページ 1370-1377, 出版日 2006年05月, 査読付
研究論文（学術雑誌）, 英語

ハラリイの一般化三並べ
伊藤大雄
信学論, J89-A巻, 6号, 掲載ページ 458--469, 出版日 2006年, 査読付
研究論文（学術雑誌）, 日本語

Efficient methods of determining DNA probe sequences
ITO Hiro; IWAMA Kazuo; TAMURA Takeyuki
IEICE Transactions, E89-A巻, 5号, 掲載ページ 1292--1298, 出版日 2006年, 査読付
研究論文（学術雑誌）, 英語

Two equivalent measures on weighted hypergraphs
ITO Hiro; NAGAMOCHI Hiroshi
Discrete Applied Mathematics, 154巻, 掲載ページ 2330--2334, 出版日 2006年, 査読付
研究論文（学術雑誌）, 英語

Single backup table schemes for shortest-path routing
H Ito; K Iwama; Y Okabe; T Yoshihiro
THEORETICAL COMPUTER SCIENCE, 333巻, 3号, 掲載ページ 347-353, 出版日 2005年03月, 査読付
研究論文（学術雑誌）, 英語

Linear-time enumeration of isolated cliques
H Ito; K Iwama; T Osumi
ALGORITHMS - ESA 2005, 3669巻, 掲載ページ 119-130, 出版日 2005年, 査読付
研究論文（学術雑誌）, 英語

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年, 査読付
研究論文（学術雑誌）, 英語

NA-edge-connectivity augmentation problems by adding edges
HH Miwa; H Ito
JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF JAPAN, 47巻, 4号, 掲載ページ 224-243, 出版日 2004年12月, 査読付
研究論文（学術雑誌）, 英語

Subdivision of the hierarchy of H-colorable graph classes by circulant graphs
UEJIMA Akihiro; ITO Hiro
Proceedings of CTW2004 Workshop on Graphs and Combinatorial Optimization, 掲載ページ 232--236, 出版日 2004年05月, 査読付
研究論文（国際会議プロシーディングス）, 英語

C_7-coloring problem
A Uejima; H Ito; T Tsukiji
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, E87A巻, 5号, 掲載ページ 1243-1250, 出版日 2004年05月, 査読付
研究論文（学術雑誌）, 英語

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年
研究論文（国際会議プロシーディングス）, 英語

Imperfectness of data for STS-based physical mapping
H Ito; K Iwama; T Tamura
EXPLORING NEW FRONTIERS OF THEORETICAL INFORMATICS, 155巻, 掲載ページ 279-292, 出版日 2004年, 査読付
研究論文（国際会議プロシーディングス）, 英語

Avoiding routing loops on the Internet
H Ito; K Iwama; Y Okabe; T Yoshihiro
THEORY OF COMPUTING SYSTEMS, 36巻, 6号, 掲載ページ 597-609, 出版日 2003年11月, 査読付
研究論文（学術雑誌）, 英語

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, 出版日 2003年08月, 査読付
研究論文（学術雑誌）, 英語

加群上の畳込み符号による可変レートMPSK符号化変調方式
小西たつ美; 横山光雄; 上原秀幸; 伊藤大雄
信学論, 86巻, 4号, 掲載ページ 20-25, 出版日 2003年, 査読付
研究論文（学術雑誌）, 英語

Sum of edge lengths of a multigraph drawn on a convex polygon
H Ito
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 24巻, 1号, 掲載ページ 41-47, 出版日 2003年01月, 査読付
研究論文（学術雑誌）, 英語

Polynomial time computable backup tables for shortest path routing
ITO Hiro; IWAMA Kazuo; OKABE Yasuo; YOSHIHIRO Takuya
Proceedings of the 10th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2003), Proceedings in Informatics, Carleton Scientific, 17巻, 掲載ページ 163--177, 出版日 2003年, 査読付
研究論文（国際会議プロシーディングス）, 英語

Can a hypergraph cover every convex polygon?
ITO Hiro; NAGAMOCHI Hiroshi
Proceedings of the 3rd Hungarian-Japanese Symposium 2003, 掲載ページ 293--302, 出版日 2003年, 査読付
研究論文（国際会議プロシーディングス）, 英語

Source location problems considering vertex-connectivity and edge-connectivity simultaneously
H Ito; M Ito; Y Itatsu; K Nakai; H Uehara; M Yokoyama
NETWORKS, 40巻, 2号, 掲載ページ 63-70, 出版日 2002年09月, 査読付
研究論文（学術雑誌）, 英語

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, 出版日 2002年05月, 査読付
研究論文（学術雑誌）, 英語

マルチホップ無線ネットワークにおける優先領域に基づく中継制御法
北岸弓子; 上原秀幸; 山本亮; 横山光雄; 伊藤大雄
信学論, 一般社団法人電子情報通信学会, J85-B巻, 12号, 掲載ページ 2119--2128-456, 出版日 2002年, 査読付
研究論文（学術雑誌）, 日本語

端末のパケット中継機能を用いた安否確認ネットワークの検討
織田将人; 上原秀幸; 横山光雄; 伊藤大雄
信学論, J85-B巻, 12号, 掲載ページ 2037--2044, 出版日 2002年, 査読付
研究論文（学術雑誌）, 日本語

A Coloring Problem With Restrictions of Adjacent Colors
Uejima Akihiro; Ito Hiro; Uehara Hideyuki; Yokoyama Mitsuo
International Transactions in Operational Research, 9巻, 2号, 掲載ページ 183-194, 出版日 2002年, 査読付
研究論文（学術雑誌）, 英語

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, 出版日 2002年01月, 査読付
研究論文（学術雑誌）, 英語

File transfer tree problems
H Ito; H Nagamochi; Y Sugiyama; M Fujita
ALGORITHMS AND COMPUTATION, PROCEEDINGS, 2518巻, 掲載ページ 441-452, 出版日 2002年, 査読付
研究論文（学術雑誌）, 英語

Avoiding routing loops on the Internet
ITO Hiro; IWAMA Kazuo; OKABE Yasuo; YOSHIHIRO Takuya
Proceedings of the 9th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2002), Proceedings in Informatics, Carleton Scientific, 13巻, 掲載ページ 197--210, 出版日 2002年, 査読付
研究論文（国際会議プロシーディングス）, 英語

Comparing hypergraphs by areas of hyperedges drawn on a convex polygon
H Ito; H Nagamochi
DISCRETE AND COMPUTATIONAL GEOMETRY, 2866巻, 掲載ページ 176-181, 出版日 2002年, 査読付
研究論文（学術雑誌）, 英語

Minimum cost source location problem with vertex-connectivity requirements in digraphs
H Nagamochi; T Ishii; H Ito
INFORMATION PROCESSING LETTERS, 80巻, 6号, 掲載ページ 287-293, 出版日 2001年12月, 査読付
研究論文（学術雑誌）, 英語

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, 出版日 2001年11月, 査読付
研究論文（学術雑誌）, 英語

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, 出版日 2001年05月, 査読付
研究論文（学術雑誌）, 英語

Coloring problem with restrictions of adjacent colors expressed by cycles and bipartite graphs
UEJIMA Akihiro; ITO Hiro; UEHARA Hideyuki; YOKOYAMA Mitsuo
Proceedings of the 2nd Japanese-Hungarian Symposium on Discrete Mathematics and Its Application, 掲載ページ 227--236, 出版日 2001年04月, 査読付
研究論文（国際会議プロシーディングス）, 英語

Source location problem with edge-connectivity requirements in digraphs
ITO Hiro; MAKINO Kazuhisa; ARATA Kouji; ITATSU Yuichiro; FUJISHIGE Satoru
Proceedings of the 2nd Japanese-Hungarian Symposium on Discrete Mathematics and Its Application, 掲載ページ 92--97, 出版日 2001年04月, 査読付
研究論文（国際会議プロシーディングス）, 英語

Location problems based on node-connectivity, and edge-connectivity between nodes and node-subsets
M Ito; M Ito; Y Itatsu; H Uehara; M Yokoyama
ALGORITHM AND COMPUTATION, PROCEEDINGS, 1969巻, 掲載ページ 338-349, 出版日 2001年, 査読付
研究論文（学術雑誌）, 英語

レイリーフェージング通信路に有効な環上の畳込み符号
小西たつ美; 横山光雄; 上原秀幸; 伊藤大雄
信学論, J84-A巻, 3号, 掲載ページ 834--839, 出版日 2001年, 査読付
研究論文（学術雑誌）, 日本語

手数制限付き一般化詰め将棋のPSPACE 完全性について
横田雅也; 築地立家; 藤井愼二; 伊藤大雄
信学論, 一般社団法人電子情報通信学会, J84-D-I巻, 1号, 掲載ページ 58--61-61, 出版日 2001年, 査読付, 縦横Nますに王将を除く各駒がO(N)枚ずつ配置されている盤面が与えられたとき, 詰み手順があるかどうかを判定する問題を一般化つめ将棋問題と呼ぶ.伊藤らはその計算複雑さがNP困難であることを証明した.本論文では盤面とともに手数の上限を単進数で与えたときの一般化詰め将棋問題がPSPACE完全であることを証明する.
研究論文（学術雑誌）, 日本語

Sum of edge lengths of a graph drawn on a convex polygon
H Ito; H Uehara; N Yokoyama
DISCRETE AND COMPUTATIONAL GEOMETRY, 2098巻, 掲載ページ 160-166, 出版日 2001年, 査読付
研究論文（学術雑誌）, 英語

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, 出版日 2000年04月, 査読付
研究論文（学術雑誌）, 英語

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, 出版日 2000年04月, 査読付
研究論文（学術雑誌）, 英語

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, 出版日 2000年03月, 査読付
研究論文（学術雑誌）, 英語

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年, 査読付
研究論文（国際会議プロシーディングス）, 英語

NP-completeness of stage illumination problems
H Ito; H Uehara; M Yokoyama
DISCRETE AND COMPUTATIONAL GEOMETRY, 1763巻, 掲載ページ 158-165, 出版日 2000年, 査読付
研究論文（学術雑誌）, 英語

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年, 査読付
研究論文（学術雑誌）, 英語

The sum of chord lengths for convex polygons is a concave and increasing function
ITO Hiro; UEHARA Hideyuki; YOKOYAMA Mitsuo
Proceedings of the Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, 掲載ページ 79--81, 出版日 1999年03月, 査読付
研究論文（国際会議プロシーディングス）, 英語

Access control schemes for slotted ALOHA system with an adaptive array
UEHARA Hideyuki; YOKOYAMA Mitsuo; ITO Hiro
Proceedings of the 1998 International Symposium on Information Theory and Its Application (ISITA'98), 掲載ページ 142--145, 出版日 1998年10月, 査読付
研究論文（国際会議プロシーディングス）, 英語

Linear time algorithms for graph search and connectivity determination on complement graphs
H Ito; M Yokoyama
INFORMATION PROCESSING LETTERS, 66巻, 4号, 掲載ページ 209-213, 出版日 1998年05月, 査読付
研究論文（学術雑誌）, 英語

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, 出版日 1998年05月, 査読付
研究論文（学術雑誌）, 英語

Edge connectivity between nodes and node-subsets
H Ito; M Yokoyama
NETWORKS, 31巻, 3号, 掲載ページ 157-163, 出版日 1998年05月, 査読付
研究論文（学術雑誌）, 英語

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年, 査読付
研究論文（学術雑誌）, 英語

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, 出版日 1997年03月, 査読付
研究論文（学術雑誌）, 英語

Complexity and algorithm for reallocation problem
H Miwa; H Ito
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, E79A巻, 4号, 掲載ページ 461-468, 出版日 1996年04月, 査読付
研究論文（学術雑誌）, 英語

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, 出版日 1995年08月, 査読付
研究論文（学術雑誌）, 英語

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, 出版日 1995年03月, 査読付
研究論文（学術雑誌）, 英語

フロー割当によるネットワーク性能推定法
松崎隆一; 伊藤大雄
信学論, J78-B-I巻, 3号, 掲載ページ 825--836, 出版日 1995年, 査読付
研究論文（学術雑誌）, 日本語

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年
研究論文（国際会議プロシーディングス）, 英語

グラフにおける節点・領域連結度について
伊藤大雄
電気学会論文誌, 114-C巻, 4号, 掲載ページ 463--469-469, 出版日 1994年, 査読付
研究論文（学術雑誌）, 日本語

Hybrid control strategies for advanced network control and their intelligent decision support system
INOUE Akiya; ITO Hiro; YAMAMOTO Hisao
Proceedings of the Fifth International Network Planning Symposium (NETWORKS'92), 掲載ページ 37--42, 出版日 1992年05月, 査読付
研究論文（国際会議プロシーディングス）, 英語

ダイナミックルーチングのための迂回候補群作成法
伊藤大雄; 井上明也
信学論, J75-B-I巻, 5号, 掲載ページ 323--332-332, 出版日 1992年, 査読付
研究論文（学術雑誌）, 日本語

経由枝数に制限を持つ多品種流問題
伊藤大雄
信学論, J75-A巻, 3号, 掲載ページ 643--645, 出版日 1992年, 査読付
研究論文（学術雑誌）, 日本語

ADVANCED CALL-LEVEL ROUTING SCHEMES FOR HYBRID CONTROLLED DYNAMIC ROUTING
A INOUE; H YAMAMOTO; H ITO; K MASE
IEICE TRANSACTIONS ON COMMUNICATIONS ELECTRONICS INFORMATION AND SYSTEMS, 74巻, 12号, 掲載ページ 4025-4033, 出版日 1991年12月, 査読付
研究論文（学術雑誌）, 英語

ましゅの定数時間検査
兜石鼓太郎; 伊藤大雄
ラスト(シニア)オーサー, 出版日 2024年03月, 信学技報, COMP2023巻, 2024-03号, 掲載ページ 14-21, 研究発表ペーパー・要旨（全国大会，その他学術会議）

ネコ教授が楽しむ数学・計算機科学講義
伊藤大雄
筆頭著者, 出版日 2024年01月, 数理解析研究所講究録, 2275巻, 掲載ページ 12-17, 招待

Unfolding and Dissection of Multiple Cubes, Tetrahedra, and Doubly Covered Squares
Zachary Abel; Brad Ballinger; Erik D. Demaine; Martin L. Demaine; Jeff Erickson; Adam Hesterberg; Hiro Ito; Irina Kostitsyna; Jayson Lynch; Ryuhei Uehara
In this paper, we introduce the notion of "rep-cube": a net of a cube that can be divided into multiple polygons, each of which can be folded into a cube. This notion is inspired by the notion of polyomino and rep-tile; both are introduced by Solomon W. Golomb, and well investigated in the recreational mathematics society. We prove that there are infinitely many distinct rep-cubes. We also extend this notion to doubly covered squares and regular tetrahedra.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.25(2017) (online)DOI http://dx.doi.org/10.2197/ipsjjip.25.610------------------------------In this paper, we introduce the notion of "rep-cube": a net of a cube that can be divided into multiple polygons, each of which can be folded into a cube. This notion is inspired by the notion of polyomino and rep-tile; both are introduced by Solomon W. Golomb, and well investigated in the recreational mathematics society. We prove that there are infinitely many distinct rep-cubes. We also extend this notion to doubly covered squares and regular tetrahedra.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.25(2017) (online)DOI http://dx.doi.org/10.2197/ipsjjip.25.610------------------------------, 出版日 2017年08月15日, 情報処理学会論文誌, 58巻, 8号, 英語, 1882-7764, 170000148837, AN00116647

A Much Faster Algorithm for Finding a Maximum Clique with Computational Experiments
Etsuji Tomita; Sora Matsuzaki; Atsuki Nagao; Hiro Ito; Mitsuo Wakatsuki
We present further improvements to a branch-and-bound maximum-clique-finding algorithm MCS (WALCOM 2010, LNCS 5942, pp.191-203) that was shown to be fast. First, we employ a variant of an efficient approximation algorithm KLS for finding a maximum clique. Second, we make use of appropriate sorting of vertices only near the root of the search tree. Third, we employ a lightened approximate coloring mainly near the leaves of the search tree. A new algorithm obtained from MCS with the above improvements is named k5_MCT. It is shown that k5_MCT is much faster than MCS by extensive computational experiments. In particular, k5_MCT is shown to be faster than MCS for gen400_p0.9_75, gen400_p0.9_65 and gen400_p0.9_55 by over 81,000, 39,000 and 19,000 times, respectively.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.25(2017) (online)DOI http://dx.doi.org/10.2197/ipsjjip.25.667------------------------------We present further improvements to a branch-and-bound maximum-clique-finding algorithm MCS (WALCOM 2010, LNCS 5942, pp.191-203) that was shown to be fast. First, we employ a variant of an efficient approximation algorithm KLS for finding a maximum clique. Second, we make use of appropriate sorting of vertices only near the root of the search tree. Third, we employ a lightened approximate coloring mainly near the leaves of the search tree. A new algorithm obtained from MCS with the above improvements is named k5_MCT. It is shown that k5_MCT is much faster than MCS by extensive computational experiments. In particular, k5_MCT is shown to be faster than MCS for gen400_p0.9_75, gen400_p0.9_65 and gen400_p0.9_55 by over 81,000, 39,000 and 19,000 times, respectively.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.25(2017) (online)DOI http://dx.doi.org/10.2197/ipsjjip.25.667------------------------------, 出版日 2017年08月15日, 情報処理学会論文誌, 58巻, 8号, 英語, 1882-7764, 170000148844, AN00116647

Bumpy Pyramid Folding Problem (システム数理と応用)
ABEL ZACHARY R.; DEMAINE ERIK D.; DEMAINE MARTIN L.; ITO HIRO; SNOEYINK JACK; UEHARA RYUHEI
Folding problems are investigated for a class of petal (or star-like) polygons P, with an n-polygonal base B surrounded by a sequence of triangles for which adjacent pairs of sides have equal length. Linear time algorithms using constant precision are given to determine if P can fold to a pyramid with flat base B, and to determine a triangulation of B (crease pattern) that allows folding into a bumpy pyramid that is convex. By Alexandrov's theorem, the crease pattern is unique if it exists, but the general algorithm known for this theorem is pseudo-polynomial, with very large running time; ours is the first efficient algorithm for Alexandrov's theorem for a special class of polyhedra. We also show a polynomial time algorithm that finds the crease pattern to produce the maximum volume bumpy pyramid., 一般社団法人電子情報通信学会, 出版日 2013年11月06日, 電子情報通信学会技術研究報告 = IEICE technical report : 信学技報, 113巻, 279号, 掲載ページ 113-119, 英語, 0913-5685, 110009886695, AA12529664

Bumpy Pyramid Folding Problem
ZacharyR.Abel; ErikD.Demaine; MartinL.Demaine; Hiro Ito; Jack Snoeyink; Ryuhei Uehara
Folding problems are investigated for a class of petal (or star-like) polygons P, with an n-polygonal base B surrounded by a sequence of triangles for which adjacent pairs of sides have equal length. Linear time algorithms using constant precision are given to determine if P can fold to a pyramid with flat base B, and to determine a triangulation of B (crease pattern) that allows folding into a bumpy pyramid that is convex. By Alexandrov's theorem, the crease pattern is unique if it exists, but the general algorithm known for this theorem is pseudo-polynomial, with very large running time; ours is the first efficient algorithm for Alexandrov's theorem for a special class of polyhedra. We also show a polynomial time algorithm that finds the crease pattern to produce the maximum volume bumpy pyramid.Folding problems are investigated for a class of petal (or star-like) polygons P, with an n-polygonal base B surrounded by a sequence of triangles for which adjacent pairs of sides have equal length. Linear time algorithms using constant precision are given to determine if P can fold to a pyramid with flat base B, and to determine a triangulation of B (crease pattern) that allows folding into a bumpy pyramid that is convex. By Alexandrov's theorem, the crease pattern is unique if it exists, but the general algorithm known for this theorem is pseudo-polynomial, with very large running time; ours is the first efficient algorithm for Alexandrov's theorem for a special class of polyhedra. We also show a polynomial time algorithm that finds the crease pattern to produce the maximum volume bumpy pyramid., 一般社団法人情報処理学会, 出版日 2013年10月30日, 研究報告アルゴリズム（AL）, 2013巻, 19号, 掲載ページ 1-7, 英語, 0919-6072, 110009614899, AN1009593X

On A Generalization of River Crossing Problems
Hiro Ito; Stefan Langerman; Yuichi Yoshida
出版日 2013年04月, Proc. 6th Annual Meeting of Asian Association for Algorithms and Computation (AAAC), 英語, 査読付, 研究発表ペーパー・要旨（国際会議）

Testing graph rigidity in constant time
Hiro Ito; Shin-ichi Tanigawa; Yuichi Yoshida
出版日 2011年04月, Proc. 4th Annual Meeting of Asian Association for Algorithms and Computation (AAAC), 英語, 研究発表ペーパー・要旨（国際会議）

ナップサック問題に対する定数時間近似アルゴリズム
伊藤 大雄; 清島 奨; 吉田 悠一
社団法人電子情報通信学会, 出版日 2011年03月, 電子情報通信学会技術研究報告. COMP, コンピュテーション, 110巻, 464号, 掲載ページ 29-36, 日本語, 0913-5685, 110008689181

An almost optimal algorithm for Winkler's sorting pairs in bins (コンピュテーシヨン)
Ito Hiro; Teruyama Junichi; Yoshida Yuichi
We investigate the following sorting puzzle: We are given n bins with two balls in each bin. Balls in the ith bin are numbered n-i+1. We can swap two balls from adjacent bins. How many number of swaps are needed in order to sort balls, i.e., move every ball to the bin with the same number. For this puzzle the best known solution requires almost (4n^2)/5 swaps. In this paper, we show an algorithm which solves this puzzle using less than (2n^2)/3 swaps. Since it is known that the lower bound of the number of swaps is [numerical formula],our result is almost tight. Futhermore, we show that for n=2^k+1(k〓0) the algorithm is optimal., 一般社団法人電子情報通信学会, 出版日 2010年01月18日, 電子情報通信学会技術研究報告. COMP, コンピュテーション, 109巻, 391号, 掲載ページ 45-49, 英語, 0913-5685, 110008004172, AN10013152

STOC2009参加報告
伊藤 大雄; 吉田 悠一
一般社団法人情報処理学会, 出版日 2009年08月15日, 情報処理, 50巻, 8号, 掲載ページ 794-797, 日本語, 0447-8053, 110007339758

Constant-time approximations using minimum value search for independent sets and matchings
Yuichi Yoshida; Masaki Yamamoto; Hiro Ito
出版日 2009年04月, Proc. 2nd Annual Meeting of Asian Association for Algorithms and Computation (AAAC), 英語, 研究発表ペーパー・要旨（国際会議）

DS-1-1 最大独立集合と最大マッチングに対する定数時間近似アルゴリズムの改善(DS-1. COMP学生シンポジウム,シンポジウムセッション)
吉田 悠一; 山本 真基; 伊藤 大雄
社団法人電子情報通信学会, 出版日 2009年03月04日, 電子情報通信学会総合大会講演論文集, 2009巻, 1号, 掲載ページ "S-21"-"S-22", 日本語, 110007094594

Property testing on k-vertex-connectivity of graphs (コンピュテーション)
吉田 悠一; 伊藤 大雄
最大頂点次数が与えられた定数以下の無向グラフのk点連結性を検査するアルゴリズムを示す。このアルゴリズムの計算量は入力グラフの頂点数、枝数に依らない定数である。頂点数n、最大次数dのグラフGがk点連結性からε遠隔であるとは、そのグラフを最大頂点次数がd以下のk点連結なグラフに変形するのに、少なくともεdn/2本の枝を追加および削除しなければならないことを言う。本アルゴリズムはグラフがk点連結のときは常にグラフを受理し、グラフがk点連結性からε遠隔であるときは、確率2/3以上で拒否する。計算時間は、入力グラフがk-1点連結なものに限定されている時、O(d(c/(εd))^klog1/(εd))(c>1は定数)時間であり、入力グラフが一般のときはO(d((ck)/(εd))^klogk/(εd))(c>1は定数)時間である。本アルゴリズムは一般のk≧4に対してk点連結性を定数時間で検査する初めてのアルゴリズムである。, 一般社団法人電子情報通信学会, 出版日 2008年06月16日, 電子情報通信学会技術研究報告, 108巻, 89号, 掲載ページ 49-55, 英語, 0913-5685, 110006951168, AN10013152

On k-connectivity testing in degree-bounded graphs
Yuichi Yoshida; Hiro Ito
出版日 2008年04月, Proc. 1st Annual Meeting of Asian Association for Algorithms and Computation (AAAC), 英語, 研究発表ペーパー・要旨（国際会議）

有向グラフにおけるk枝連結性の検査
吉田 悠一; 伊藤 大雄
社団法人電子情報通信学会, 出版日 2007年06月, 電子情報通信学会技術研究報告. COMP, コンピュテーション, 107巻, 127号, 掲載ページ 17-23, 日本語, 0913-5685, 110006343677

Efficient Methods for Determining DNA Probe Orders
ITO Hiro; IWAMA Kazuo; TAMURA Takeyuki
In STS-based mapping, it is necessary to obtain the correct order of probes in a DNA sequence from a given set of fragments or an equivalently a hybridization matrix A. It is well-known that the problem is formulated as the combinatorial problem of obtaining a permutation of A's columns so that the resulting matrix has a consecutive-one property. If the data (the hybridization matrix) is error free and includes enough information, then the above column order uniquely determines the correct order of the probes. Unfortunately this does not hold if the data include errors, and this has been a popular research target in computational biology. Even if there is no error, ambiguities in the probe order may still remain. This in fact happens because of the lack of some information regarding the data, but almost no further investigation has previously been made. In this paper, we define a measure of such imperfectness of the data as the minimum amount of the additional fragments that are needed to uniquely fix the probe order. Polynomial-time algorithms to compute such additional fragments of the minimum cost are presented. A computer simulation using genes of human chromosome 20 is also noted., 一般社団法人電子情報通信学会, 出版日 2006年05月01日, IEICE transactions on fundamentals of electronics, communications and computer sciences, 89巻, 5号, 掲載ページ 1292-1298, 英語, 0916-8508, 110007502843, AA10826239

グラフの変形操作における単純性の保存
伊藤大雄
ラベル付きグラフ上の半順序関係である、カットサイズ順序、枝長和順序、交叉操作順序の三つは同値であることが知られている。グラフGがこの半順序関係においてG'に先行するとき、GをG'に変形する交叉操作の列が存在するが、仮にGとG'の両方が単純グラフだとしても、中間に単純でないグラフが現れる可能性がある。このことは、Hakimiによる名高い次数不変変換においても同様に起こる問題である。本稿では、このような場合に単純グラフのみを介して、変形しうるか否かという問題を取り扱う。結果、Hakimiの次数不変変換については、常に単純グラフによる変形が可能であることを示した。しかし一方で、上記の半順序関係に基づく変形の場合は、例え交叉操作以外の操作も許容したとしても、与えられた操作の種類が有限だとすると、その半順序関係にありながら単純グラフのみを介しての変換ができないグラフの組が必ず存在することを証明した。Three partial orders, cut-size order, length order, and operation order, defined between labeled graphs with the same order are known to be equivalent. If G precedes G' with regard to the partial order, there is a sequence of cross-operations such that G is transformed into G' by using the sequence. Even if both G and G' are simple graphs, non-simple graphs may appear on the way of the transformation. The same problem occurs in the well-known Hakimi's d-invariant transformation. This paper considers whether we can transform them without using non-simple graphs. First, we show that we can do it in Hakimi's $d$-invariant transformation. Second, however, we prove that there is no efficient finite set of operations for the partial order's transformation in the general case., 一般社団法人情報処理学会, 出版日 2004年11月05日, 情報処理学会研究報告アルゴリズム（AL）, 2004巻, 109号, 掲載ページ 1-8, 英語, 0919-6072, 110002812555, AN1009593X

H-彩色可能なグラフのクラスの階層構造のCirculant graphs による細分化
上嶋 章宏; 伊藤大雄
p-彩色可能なグラフはC_{2p+1}-彩色可能であり，C_{2p+1}-彩色可能なグラフはp+1-彩色可能であるが，いずれも逆は成立しない(但しC_{2p+1}は長さ2p+1の閉路の補グラフである)．本発表ではこの包含関係が circulant graphsの部分集合として我々が定義するH(n k)によってさらに細分化されることを示す．この細分化は、従来から知られているC_{2p+1}による細分化をも包含する．更に平面グラフのH(n k)-彩色に対し，いくつかのNP-完全問題を示す．p-colorable graphs are C_{2p+1}-colorable, and C_{2p+1}-colorable graphs are p+1-colorable, where C_{2p+1} is the complement graph of a cycle of order 2p+1. However, the converse statements are incorrect. This paper presents that these inclusions can be subdivided by our original graphs H(n, k) which are defined as a subset of circulant graphs. The subdivided hierarchy contains the well-known inclusion of C_{2p+1}-colorable graphs. Moreover, This paper shows some NP-complete problems for planar H(n, k)-colorings., 一般社団法人情報処理学会, 出版日 2004年01月30日, 情報処理学会研究報告アルゴリズム（AL）, 2004巻, 10号, 掲載ページ 1-8, 日本語, 0919-6072, 110002811976, AN1009593X

平面グラフのC7－彩色問題
上嶋 章宏; 伊藤大雄
本稿では，グラフの点彩色問題の一般化である，H-彩色問題を扱う(但し，Hはグラフ)．特にHが奇数長閉路の補グラフC￣_p(pは節点数)である場合を取り上げ，以下の性質を示す：(1) m-彩色可能であるとき，かつそのときに限り，C￣￣￣￣_2m+1-彩色可能であるような、グラフのクラスの提示，(2) 平面グラフのC￣_7-彩色問題の NP-完全性の証明，(3) C￣_7-彩色可能であるが，3-彩色不可能な平面グラフのクラスの提示．This paper considers H-coloring problem, which is a generalization of the traditional coloring problem, where H is a graph. Especially, we deal with the case that H is the complement graph C￣_p of a cycle of order p. This paper presents as follows: (1) classes of graphs which are C￣￣￣￣_2m+1-colorable iff m-colorable, (2) C￣_7 -coloring problem of planar graphs is NP-complete, and (3) there exists a class of graphs which are not 3-colorable but C￣_7-colorable., 一般社団法人情報処理学会, 出版日 2002年09月19日, 情報処理学会研究報告アルゴリズム（AL）, 2002巻, 88号, 掲載ページ 67-74, 日本語, 0919-6072, 110002812525, AN1009593X

グラフの平面凸描画の枝長と線形カットサイズと交差操作の関係
伊藤大雄
G = (N c)を節点集合N={0 1 ... n-1}と実数の枝の重み関数c:V×V->Rによって定義されるグラフ（ネットワーク）とする。以下の３つの尺度を考える。(1) 凸多角形上にグラフを記述したときの枝長の総和、(2) 線形カットの大きさ、(3) 枝の交差処理による帰着可能性。これらの３つの尺度に関連した半順序関係を導入し、それらが同値であることを証明する。Let G=(N,c) be a graph with a vertex set N={0,1,...,n-1} and a real edge weight function c:V×V->R. Three measures for comparing two graphs are considered: (1) the sum of edge length when the graph is drawn on a convex polygon, (2) sizes of linear-cuts, and (3) reducibility by using cross-operations. Three partial orders, corresponding the measures respectively, are also introduced. This paper shows that these three partial orders are equivalent. Moreover, it presents a polynomial time algorithm for determining G \preceq G' for given G and G', where, \preceq is the partial order., 一般社団法人情報処理学会, 出版日 2002年03月15日, 情報処理学会研究報告アルゴリズム（AL）, 2002巻, 29号, 掲載ページ 27-34, 日本語, 0919-6072, 110002812482, AN1009593X

Variable Rate MPSK Coded Modulation Using Convolutional Codes over Modules
KONISHI Tatsumi; YOKOYAMA Mitsuo; UEHARA Hideyuki; ITO Hiro
In this paper, we present a new method of a variable rate MPSK coded modulation using convolutional codes over modules. We define convolutional codes over modules, and investigate some properties of the codes such as the minimum Euclidean distance and the minimum Hamming distance. If any suitable module is selected for a variable rate coded modulation system, only a single encoder and a Viterbi decoder are sufficiently to support the variable rate modulation system. Coded modulation system using new convolutional codes over Z_<12> module are evaluated by computer simulation on AWGN and Rayleigh fading channels., 一般社団法人電子情報通信学会, 出版日 2002年03月01日, IEICE transactions on fundamentals of electronics, communications and computer sciences, 85巻, 3号, 掲載ページ 729-730, 英語, 0916-8508, 110003216806, AA10826239

優先領域に基づく中継制御法を用いたマルチホップ無線ネットワークの検討
北岸 弓子; 上原 秀幸; 横山 光雄; 伊藤 大雄
マルチホップ無線ネットワークにおけるパケット配信方式の一つにフラッディング方式がある.従来のフラッディング方式では, パケットを受信した全ての端末が中継を行うためにネットワーク内のトラヒックが増加するという問題がある.トラヒックの増加は競合や衝突の増加にもつながり, パケットの到達率やスループットの劣化をまねく.本報告では優先領域に基づいて冗長なパケットの中継を制限する中継制御法を提案する.計算機シミュレーションによって性能評価を行った結果, 提案する中継制御法を用いることによってネットワーク内のトラヒックを削減し, メッセージパケットの配信率, ルート確保率を向上させることができることを示す., 一般社団法人電子情報通信学会, 出版日 2002年01月04日, 電子情報通信学会技術研究報告. DSP, ディジタル信号処理, 101巻, 539号, 掲載ページ 15-20, 日本語, 0913-5685, 110003280587, AN10060786

優先領域に基づく中継制御法を用いたマルチホップ無線ネットワークの検討
北岸 弓子; 上原 秀幸; 横山 光雄; 伊藤 大雄
マルチホップ無線ネットワークにおけるパケット配信方式の一つにフラッディング方式がある.従来のフラッディング方式では, パケットを受信した全ての端末が中継を行うためにネットワーク内のトラヒックが増加するという問題がある.トラヒックの増加は競合や衝突の増加にもつながり, パケットの到達率やスループットの劣化をまねく.本報告では優先領域に基づいて冗長なパケットの中継を制限する中継制御法を提案する.計算機シミュレーションによって性能評価を行っ結果, 提案する中継制御法を用いることによってネットワーク内のトラヒックを削減し, メッセージパケットの配信率, ルート確保率を向上させることができることを示す., 一般社団法人電子情報通信学会, 出版日 2002年01月04日, 電子情報通信学会技術研究報告. RCS, 無線通信システム, 101巻, 545号, 掲載ページ 15-20, 日本語, 0913-5685, 110003305994, AN10060822

優先領域に基づく中継制御法を用いたマルチホップ無線ネットワークの検討
北岸 弓子; 上原 秀幸; 横山 光雄; 伊藤 大雄
マルチホップ無線ネットワークにおけるパケット配信方式の一つにフラッディング方式がある.従来のフラッディング方式では, パケットを受信した全ての端末が中継を行うためにネットワーク内のトラヒックが増加するという問題がある.トラヒックの増加は競合や衝突の増加にもつながり, パケットの到達率やスループットの劣化をまねく.本報告では優先領域に基づいて冗長なパケットの中継を制限する中継制御法を提案する.計算機シミュレーションによって性能評価を行っ結果, 提案する中継制御法を用いることによってネットワーク内のトラヒックを削減し, メッセージパケットの配信率, ルート確保率を向上させることができることを示す., 一般社団法人電子情報通信学会, 出版日 2002年01月03日, 電子情報通信学会技術研究報告. SAT, 衛星通信, 101巻, 542号, 掲載ページ 15-20, 日本語, 0913-5685, 110003193844, AN10012987

A Faster and Flexible Algorithm for a Location Problem on Undirected Flow Networks
ITO Hiro; UEHARA Hideyuki; YOKOYAMA Mitsuo
For a given graph G=(V, E), edge capacities c(e) for edges e ⋳ E, and flow-demands d(v) for nodes v ⋳ V, a problem of finding the minimum size source-set S ⊊ V such that the maximum flow-amount between S and v is greater than or equal to d(v) for every v ⋳ V is called generalized plural cover problem (GPC). For this problem, O(np・s(n, m)) time algorithm is presented, where n, m, and p is the number of nodes, edges, and different values of d(v), respectively, and s(n, m) is the time required to solve the maximum flow problem of a graph with n nodes and m edges. This algorithm also constructs a set of optimal solutions in the same time. This property is convenient for applying it to real problems, because other constraints can also be taken into account., 一般社団法人電子情報通信学会, 出版日 2000年04月25日, IEICE transactions on fundamentals of electronics, communications and computer sciences, 83巻, 4号, 掲載ページ 704-712, 英語, 0916-8508, 110003208579, AA10826239

一般化詰め将棋問題の計算複雑さ : 小駒図式、成駒無し、還元玉、都詰の考慮
伊藤 大雄; 藤井 愼二; 上原 秀幸; 横山 光雄
詰め将棋の盤面をn×nにし、王将以外の駒を0(n)個の用意した、一般化詰め将棋問題の計算複雑さについて論じる。詰め将棋には見た目や詰め方などに面白みを出すため、駒の初期配置に工夫をしたり、正解の詰め手順に美しい趣向が隠されている様な、趣向詰めというものがある。本稿では、飛車と角を使用しない「小駒図式」、初期配置に成り駒が無い「成り駒無し」、王将が初期配置で居た場所に戻って詰む「還元玉」、王将が中央のマスで詰む「都詰め」の4つの趣向を同時に満たすものに限定しても一般化詰め将棋問題がNP困難であることを証明する。, 一般社団法人電子情報通信学会, 出版日 1999年07月21日, 電子情報通信学会技術研究報告. COMP, コンピュテーション, 99巻, 194号, 掲載ページ 17-24, 日本語, 0913-5685, 110003191783, AN10013152

遠近問題を考慮した送信許可確率可変スロットアロハ方式の検討
森山 崇元; 上原 秀幸; 横山 光雄; 伊藤 大雄
スロットアロハ方式等のパケット無線ネットワークにおけるスループット特性向上の手法としてのアクセス制御方式がいくつか提案されているが、このようなスループット向上は全ての端末に平等に与えられるわけではない。遠近問題を考慮した場合、基地局に近い端末に比べ、遠いところになる端末のスループットが著しく劣化するという不平等が生じる。そこで本稿では遠近問題を考慮したスロットアロハ方式において、チャネルロードに応じてパケット送信許可確率を適応的に変化させることにより、チャネルロードが大きいところでも最大スループットを維持しつつ、かつ基地局に近い端末と遠い端末の間で同等のスループット特性が得られることを計算機シミュレーションにより示す。, 一般社団法人電子情報通信学会, 出版日 1998年08月20日, 電子情報通信学会技術研究報告. SSE, 交換システム, 98巻, 240号, 掲載ページ 73-78, 日本語, 0913-5685, 110003235127, AN10060742

遠近問題を考慮した送信許可確率可変スロットアロハ方式の検討
森山 崇元; 上原 秀幸; 横山 光雄; 伊藤 大雄
スロットアロハ方式等のパケット無線ネットワークにおけるスループット特性向上の手法としてのアクセス制御方式がいくつか提案されているが、このようなスループット向上は全ての端末に平等に与えられるわけではない。遠近問題を考慮した場合、基地局に近い端末に比べ、遠いところになる端末のスループットが著しく劣化するという不平等が生じる。そこで本稿では遠近問題を考慮したスロットアロハ方式において、チャネルロードに応じてパケット送信許可確率を適応的に変化させることにより、チャネルロードが大きいところでも最大スループットを維持しつつ、かつ基地局に近い端末と遠い端末の間で同等のスループット特性が得られることを計算機シミュレーションにより示す。, 一般社団法人電子情報通信学会, 出版日 1998年04月23日, 電子情報通信学会技術研究報告. RCS, 無線通信システム, 98巻, 20号, 掲載ページ 73-78, 日本語, 110003305076, AN10060822

各節点の需要が異なる最小流入点集合配置問題
伊藤 大雄; 横山 光雄
各枝e∈Eに容量c(e)が与えられたフローネットワーク(G=(V,E),c)と各節点v∈Vの需要d(v)が与えられたとき、任意のv∈Vに対しv,T間の最大流がd(v)以上となるT⊆Vで要素数|T|が最小であるものを求める問題、最小流入点集合配置問題(Minimum size flow-sink-set location problem; FSSL)に対しO(np s(n,m))時間の解法を与えた。但しn,mは各々節点数と枝数、pはd(v)のうち異なるものの数、s(n,m)は2点間の最大流を求めるのに要する時間である。, 一般社団法人電子情報通信学会, 出版日 1997年05月30日, 電子情報通信学会技術研究報告. COMP, コンピュテーション, 97巻, 83号, 掲載ページ 41-48, 英語, 110003191267, AN10013152

（n-p）-点連結性のO（m+np3.5）時間判定法
伊藤大雄; 横山 光雄
与えられたグラフG=(，)、整数1〓p〓nに対し、Gが(?)?点連結であるか否かを判定し、(?)?点連結である場合にはその点連結度も計算するO(+np^<3．5>）時間のアルゴリズムを与える（但しn=|V|，m=|E|）。また、与えられたグラフの点連結度を計算するO(+n(?K(））^<3．5>）時間のアルゴリズムも与える。これら2つのアルゴリズムはそれぞれ同じ計算時間のオーダーで、与えられたグラフの補グラフG^cに関して(?)?点連結性の判定や点連結度の計算問題を解くアルゴリズムにも拡張できる。For a given graph G=(V,E) and a given integer 1〓p〓n, an O(m+np^<3.5>) time algorithm for determining whether or not G is (n-p)-node-connected and also calculating the node-connectivity when G is (n-p)-node-connected is presented, where n=|V| and m=|E|. For calculation of the node-connectivity of a given graph G, an O(m+n(n-K(G))^<3.5>) time algorithm is also presented. These two algorithms can be extended to the same problems on the complement graph of a given graph in the same time-complexity, respectively., 一般社団法人情報処理学会, 出版日 1996年10月17日, 情報処理学会研究報告アルゴリズム（AL）, 1996巻, 100号, 掲載ページ 57-64, 日本語, 0919-6072, 110002812266, AN1009593X

フロー割当てによるダイナミックルーチング網設計法
佐竹 孝; 伊藤 大雄; 井上 明也
ダイナミックルーチング(DR)を考慮したフロー割当てによる回線数算出法を提案する。本手法の特徴は、(1)直通路からの許容あふれ率を規定して回線数を算出する、(2)時間帯や曜日による定常的なトラヒック変動を前提とし、迂回路での疎通トラヒック量を考慮して回線数を算出する、(3)DR導入網を運用・管理していくために直通路, 迂回路それぞれで運ばれるトラヒック量を把握することが容易となる、ことである。また、例としてSTR(State-and Time-dependent Routing)網に本手法を適用し、計算機実験により直通設計と比較して回線数削減効果が得られることを示す。, 一般社団法人電子情報通信学会, 出版日 1993年10月22日, 電子情報通信学会技術研究報告. IN, 情報ネットワーク, 93巻, 291号, 掲載ページ 43-50, 日本語, 110003196095, AN10013072

フロー割当によるネットワーク性能推定法の評価
松崎 隆一; 伊藤 大雄
ダイナミックルーチング制御を有する回線交換網の設計・管理のために、「網機構条件、トラヒック条件、ルーチング条件を入力として、各回線群上にどの対地間交流呼量がどれだけ流れるかを算出する」問題を解くことが重要である。実網が大規模かつ複雑であることを考慮して、発見的なフロー割当手法の適用により、高速に計算する解法を提案する。本解法は厳密に関係式で表現できない場合にも適用でき、網条件の変化等で解法が影響を受けにくいという利点がある。数値実験により、提案手法の有効性を検証する。, 一般社団法人電子情報通信学会, 出版日 1993年10月01日, 電子情報通信学会技術研究報告. SSE, 交換システム, 93巻, 257号, 掲載ページ 135-140, 日本語, 0913-5685, 110003235016, AN10060742

STR網におけるトラヒック流推定のためのフロー割当法の検討
松崎隆一; 伊藤大雄; 井上明也
出版日 1993年, 電子情報通信学会大会講演論文集, 1993巻, Shunki Pt 3号, 1349-1369, 200902120344424150

ダイナミックルーチングSTRを考慮した回線算出法
佐竹孝; 伊藤大雄; 井上明也
出版日 1993年, 電子情報通信学会大会講演論文集, 1993巻, Shuki Pt 3号, 1349-1369, 200902145349858002

特集 ディジタル中継網におけるダイナミックルーチング方式の開発 ダイナミックルーチング(STR)の自律的迂回ルート選択機能とその性能評価
井上明也; 伊藤大雄
出版日 1992年, NTT R & D, 41巻, 6号, 0915-2326, 200902016074400480

ルーチングにおけるハイブリッド制御の効果
伊藤大雄; 井上明也
出版日 1992年, 電子情報通信学会大会講演論文集, 1992巻, Shunki Pt 3号, 1349-1369, 200902058704730586

迂回候補群作成問題に関する発見的算法の効果 LPを用いた解法との比較
伊藤大雄; 井上明也
出版日 1991年, 電子情報通信学会全国大会講演論文集, 1991巻, Spring Pt 3号, 200902064613874488

STRにおける迂回候補群作成法の予測誤り耐力の評価
伊藤大雄; 井上明也
出版日 1991年, 電子情報通信学会大会講演論文集, 1991巻, Shuki Pt 3号, 1349-1369, 200902068983630516

電話網における迂回候補群作成アルゴリズム
伊藤大雄; 井上明也
出版日 1990年, 電子情報通信学会技術研究報告, 89巻, 418(IN89 113-121)号, 0913-5685, 200902002701244782

電話網における迂回候補群作成アルゴリズム
伊藤大雄; 井上明也
出版日 1990年, 電子情報通信学会全国大会講演論文集, 1990巻, Spring Pt.3号, 200902064111600449

イラストで学ぶ離散数学
伊藤大雄
教科書・概説・概論, 日本語, 単著, 講談社, 出版日 2019年09月07日, ISBN 9784065170014

データ構造とアルゴリズム（コンピュータサイエンス教科書シリーズ ２）
伊藤大雄
教科書・概説・概論, 日本語, 単著, コロナ社, 出版日 2017年09月28日, ISBN 9784339027020

ビッグデータ・マネジメント --- データサイエンティストのためのデータ利活用技術と事例
嶋田茂; 伊藤大雄
一般書・啓蒙書, 日本語, 共著, 第１編 第１章 第１節 ビッグデータの高速処理に向けた超高速アルゴリズムと計算理論, （株）エヌ・ティー・エス, 出版日 2014年03月10日, ISBN 9784864690843

離散数学のすすめ
伊藤大雄; 宇野裕之; 伊藤大雄; 名 著
一般書・啓蒙書, 日本語, 編者(編著者), 編集 および まえがき プロローグ「離散数学へのいざない」 第４章「最短路問題」 第７章「ケーキ分割問題」 第９章「フランク・ハラリィの一般化三並べ」 エピローグ「論文のできるまで --- 一般化ハムサンドイッチ定理を題材にして」 あとがき, 現代数学社, 出版日 2010年05月

パズル・ゲームで楽しむ数学 --- 娯楽数学の世界
伊藤大雄
日本語, 単著, 森北出版, 出版日 2010年02月

離散幾何学における未解決問題集
秋山仁; 伊藤大雄; 訳
日本語, 共訳, 第３章「相似コピーによる詰め込みと被覆」, シュプリンガー・ジャパン, 出版日 2009年

アルゴリズム工学 --- 計算困難問題への挑戦
杉原厚吉; 茨木俊秀; 浅野孝夫; 山下雅史; 伊藤大雄
日本語, 共著, 4.10節 「２次元ハムサンドイッチ定理の一般化」, 共立出版, 出版日 2001年06月

ネットワーク設計理論（岩波講座「インターネット」第５巻）
滝根哲哉; 伊藤大雄; 西尾章治郎
日本語, 共著, 第４章「グラフ・ネットワークアルゴリズムの基本知識」 第５章「ネットワーク構成問題」, 岩波書店, 出版日 2001年06月

考える猫【フェロー記念招待講演】
伊藤大雄
口頭発表（招待・特別）, 日本語, 電子情報通信学会 コンピュテーション研究会, 招待
発表日 2024年05月09日
- 2024年05月09日

Sublinear-Time Paradigm --- How to Challenge Big Data
Hiro Ito
口頭発表（基調）, 英語, The 13th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2019), 招待, 国際会議
発表日 2019年12月13日

Generalized shogi and chess are constant-time tastable
Hiro Ito
口頭発表（招待・特別）, 英語, The 12th International Symposium on Operations Research & Its Applications (ISORA 2015), 招待, 国際会議
発表日 2015年08月

Transformation of Graphs and their Simpleness
Hiro Ito
口頭発表（招待・特別）, 英語, he Japan Conference on Discrete and Computational Geometry 2004, 招待, 国際会議
発表日 2004年10月

日本オペレーションズ・リサーチ学会

電子情報通信学会

情報処理学会

European Association for Theoretical Computer Science (EATCS)

劣線形時間パラダイムの深化
伊藤 大雄
日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(C), 25K14987
研究期間 2025年04月 - 2030年03月

劣線形時間パラダイムの展開
伊藤 大雄
日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(C), 本研究では研究代表者の提案している「劣線形時間パラダイム」を広く展開するための理論研究を行っている。２０２１年度の主な成果は以下の通りである。 (I) 漸進型アルゴリズム(progressive algorithm)の結果をまとめた論文が論文誌に採録・出版された。「漸進型アルゴリズム」とは、データを徐々に読み込みながら段々と精度の高い解を求めていく手法であり、研究代表者によって提案されたものである。我々はこれまでに、「定数時間アルゴリズム」と「全てのデータを読み込む線形以上の計算時間のアルゴリズム」の両者が存在する任意の問題に対し、オーダの意味での各々の計算時間を悪化させることなく、両者を円滑に繋げる漸進型アルゴリズムが構築できることを証明した。これは片側誤り、両側誤りどちらにも適用可能であり、また本技法はグラフに限らず、どのような対象、モデルに対しても適用可能であると考えられ、非常に一般性のある結果である。(II) 機器をスリープ状態にしておくことで再起動の際の時間やエネルギー消費量の節減を図る制御は広く行われている。しかしスリープ状態は少しだが電力を消費し続けるので、長く保つと逆に損になる。この問題はオンライン問題の一種の「スキーレンタル問題」という形で定式化され、その競合比（小さいほど良く、１が最適）は２でこれ以上改善出来ないことが既存研究によって証明され、それが常識とされてきた。しかしその競合比２を与えるアルゴリズムは、最悪に備える為に多くの場合で明らかに無駄と考えられる動作をせざるを得なかった。そこで担当者は、競合比を2+ε（∀ε>0）と僅かに緩和することで、多くの実用的な場合にほぼ無駄が無い様に制御する方法を考案した。その結果を論文誌に投稿し採録・出版された。, 20K11671
研究期間 2020年04月01日 - 2023年03月31日

効率的な最大および極大クリーク抽出アルゴリズムの開発と応用
富田 悦次; 若月 光夫; 西野 哲朗; 伊藤 大雄
日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(C), 最大クリーク厳密解抽出の分枝限定アルゴリズムに対するこれまでの研究により，最大クリークの近似解が非常に有効に活用出来ることを明らかにしてきている．その近似精度が良くなれば分枝限定はより有効に働く．しかし，近似解抽出のために時間を要すると，総実行時間としては必ずしも短縮とはならず，近似精度と時間との兼ね合いが重要となる．そこで先ず，最大クリーク近似解の抽出を一層高速化し，その上で精度を向上させることにより，総合的に最大クリーク厳密解抽出を効率化した． 続いて，分枝限定のために近似彩色だけでなくMaxSATも用いることにより分枝限定がより強力化されることをこれまでに確認してきたが，MaxSATあるいはその簡略形実行のためのオーバーヘッドの大きさが最大クリーク厳密解抽出総実行時間短縮の妨げとなっていた．これに対しては，MaxSATの簡略形と従来提唱してきていた再番号付け（再彩色）との類似性に着目して両者を融合させることにより，これまでよりも少ないオーバーヘッドによって，有効な分枝限定効果を発揮出来るようにした．さらに，分枝限定アルゴリズムの内部動作は入力グラフの特徴に応じて効率が左右されるため，出来る限り効率がより発揮されるようにと内部動作を適応的に切り替えるようにした． 以上を総合することにより，最大クリーク厳密解抽出のための従来の分枝限定アルゴリズムを有意に高速化することに成功した． このような最大クリーク厳密解抽出アルゴリズムは，容易に最大クリーク全列挙アルゴリズムへと拡張出来る．これにより，符号理論における最良な多元単一削除訂正符号の構成に関しての新たな知見を得ることが出来た． 極大クリーク全列挙問題についてもさらに理論的，実験的に検討を続け，有効な進展結果を得た．, 17K00006
研究期間 2017年04月01日 - 2022年03月31日

劣線形時間パラダイム
伊藤 大雄
日本学術振興会, 科学研究費助成事業, 電気通信大学, 挑戦的萌芽研究, 本研究では、「劣線形時間パラダイム」の基本技術の確立を目的として行った。本研究期間における顕著な成果は、WebやSNSなど、複雑ネットワークと呼ばれる現実的な巨大グラフに対する万能定数時間アルゴリズムの提案である。すなわち、複雑ネットワークをモデル化したHSF (Hierarchical Scale Free) というマルチグラフの無限集合を定義し、それに対しては任意の性質が定数時間検査可能であることを証明した。これは疎でありかつ次数上限を持たない、所謂一般グラフと呼ばれる枠組みの非自明なクラスに対する初めての万能定数時間アルゴリズムである。, 15K11985
研究期間 2015年04月01日 - 2019年03月31日

最大および極大クリーク抽出アルゴリズムの高効率化と応用
富田 悦次; 若月 光夫; 西野 哲朗; 伊藤 大雄
日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(C), 最大クリーク抽出のための分枝限定アルゴリズムに対し，近似最大クリーク抽出アルゴリズムを効果的に組合せ，さらに節点整列と近似彩色を適切に適用することにより，実働上一層の高効率化を達成した．また理論的には，最大クリーク問題が多項式時間的高速に可解となる，よりゆるやかな条件およびアルゴリズムを与えた． 極大クリーク全列挙アルゴリズムについては，それを疑似極大クリークの全列挙までを扱えるように拡張し，ネットワーク解析への応用に対して有効性が確認された．, 25330009
研究期間 2013年04月01日 - 2018年03月31日

情報理論・符号理論からの計算限界研究
河原林 健一; 脊戸 和寿; 玉置 卓; 伊藤 大雄; 吉田 悠一
日本学術振興会, 科学研究費助成事業, 国立情報学研究所, 新学術領域研究(研究領域提案型), 情報理論・符号理論など離散数学における最先端の解析手法を使いこなし発展させることで, 計算限界解明の研究を進展させた. 具体的には(1) 劣線形時間計算における定数時間検査可能性の特徴付けや論理回路クラスの分離等, 種々のP対NP問題の類似の解決,(2) 3彩色問題に対する多項式時間近似アルゴリズムの世界記録更新等, グラフや制約充足問題に関する基本的な計算問題の計算複雑性の精微な解析,(3) (1)(2) の成果に基づいた, 劣線形時間計算やグラフアルゴリズムの機械学習や大規模データ処理等の分野への応用, が挙げられる., 24106003
研究期間 2012年06月28日 - 2017年03月31日

データの巨大化から生じる不完全情報への対処に主眼をおいた近似計算
岩間 一雄; エイビス デイビッド; 宮崎 修一; 玉置 卓; 伊藤 大雄; 堀山 貴史; 吉田 悠一; 岡本 和也; 脊戸 和寿; 川原 純; 上野 賢哉
日本学術振興会, 科学研究費助成事業, 京都大学, 基盤研究(A), 不完全情報をいかに扱うかが現代アルゴリズムの大きな課題になっている． 本研究では「データの巨大化から生じる不完全情報に対処するための近似計算における，できるだけ一般性の高いアルゴリズム設計理論の体系化」を目的として研究を行った． 結果として，グラフ問題，アルゴリズム的ゲーム理論，乱化に関する基礎理論の様々な問題において，情報の不完全性を克服できるアルゴリズムの設計と解析に成功した．, 25240002
研究期間 2013年04月01日 - 2016年03月31日

ゲーム解析の新パラダイム
伊藤 大雄
日本学術振興会, 科学研究費助成事業, 電気通信大学, 挑戦的萌芽研究, ゲーム・パズルに関する劣線形時間アルゴリズムを中心に、これまでに無い枠組みという視点から研究を推進し、以下の結果を得た。 (I) ケーキ分割問題に対し、劣線形時間アルゴリズムの枠組みを与え、具体的なアルゴリズムを提案した。(II) 一般化将棋問題に対し、定数時間アルゴリズムを提案した。(III) 川渡り問題に対し、「禁止状態」を入力とした問題を提案し、グラフのエキスパンダーを利用した新しい多項式時間アルゴリズムを提案した。(IV) n手からなる一般化ジャンケンについて、異なる手の間に引分けを考慮した問題に対し、引分けの総数の厳密な上下限を導くなどの諸性質を得た。, 24650006
研究期間 2012年04月01日 - 2016年03月31日

ゲーム情報学：Ａｎｄ－Ｏｒ木の探索とゲーム・パズルの難しさの研究
岩田 茂樹; 武永 康彦; 笠井 琢美; 伊藤 大雄
日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(C), 本研究は、ゲーム情報学全般にわたる研究のうち、(1) And-Or 木のコンピュータによる探索、と (2) ゲームやパズルの複雑さに関する研究を行う、ことを目的とする。 And-Or 木（ゲーム木）のコンピュータによる探索では通常、評価関数が用いられる。ゲーム木の自然なモデルを定め、ゲーム木のある深さにおいて深さ優先探索により探索する局面数を考える。完全な評価関数に確率 p(0研究期間 2011年 - 2013年

空間的な情報補填を可能にするアルゴリズムの研究
岩間 一雄; エイビス デイビッド; 宮崎 修一; 玉置 卓; 伊藤 大雄; 加藤 直樹; 徳山 豪; 山下 雅史; 渡辺 治; 堀山 貴史; 川原 純; 森住 大樹; 伊藤 大雄
日本学術振興会, 科学研究費助成事業, 京都大学, 基盤研究(A), 不完全情報をいかに扱うかが現代アルゴリズムの大きな課題になっている.本研究では「空間的な情報の不完全性を克服できるアルゴリズムに関して,その設計技法と評価手法を含めた総合的体系を作り上げること」を目的として研究を行った.結果として,グラフ問題,アルゴリズム的ゲーム理論,乱化に関する基礎理論の様々な問題において,空間的な情報の不完全性を克服できるアルゴリズムの設計と解析に成功した., 22240001
研究期間 2010年 - 2012年

巨大情報からの超高速情報抽出アルゴリズムの研究
伊藤 大雄; 岩間 一雄
日本学術振興会, 科学研究費助成事業, 京都大学, 基盤研究(C), データが膨大である対象をあつかうための、高速アルゴリズムとその計算量の下界値に対して研究を行った。特に、対象となるデータのうちのごく一部、定数個しか見ないで問題を解くという定数時間アルゴリズムを中心に研究し、グラフの最大独立集合や最大マッチングのサイズの近似、外平面性の検査、疎性マトロイドのランクの近似、ナップザック問題の解の近似に対して、高速な定数時間アルゴリズムを与えた。また、線形下界値を示す技法をいくつか与えた。他に、ユニットディスクグラフを描画領域でパラメータ化し、いくつかの問題に対しFPTアルゴリズムと下界値を与えた。, 21500014
研究期間 2009年 - 2011年

情報補填を可能にするアルゴリズムの設計と解析
岩間 一雄; 加藤 直樹; 伊藤 大雄; 宮崎 修一; 玉置 卓; 杉原 厚吉; 徳山 豪; 山下 雅史; 渡辺 治; 堀山 貴史; 杉原 厚吉; 徳山 豪; 山下 雅史; 渡辺 治
日本学術振興会, 科学研究費助成事業, 京都大学, 基盤研究(A), 入力情報の不完全性をいかに克服する(情報を補填する)かが現代アルゴリズムの大きな課題となっている,本研究では,そのようなアルゴリズムが有すべき性質を厳密に議論し,具体的な設計技法と評価手法を含めた体系を作り上げることを目的として,研究を行った.結果として,オンライン,ネットワーク,マッチング,確率,幾何,分散等多岐にわたる分野で効率よいアルゴリズムの開発に成功した., 19200001
研究期間 2007年 - 2009年

巨大情報のアルゴリズム的超圧縮技術の研究
伊藤 大雄; 岩間 一雄; 中村 義作; 福田 宏; 福田 宏; 中村 義作
日本学術振興会, 科学研究費助成事業, 京都大学, 基盤研究(C), 指数爆発あるいは入力そのものが巨大である等の理由で従来困難とされてきた問題に対し、本来の目的を失うことなく視点を変えることによって効率的に解くことができる技法について研究した.特にグラフに「孤立」の概念を導入して部分グラフを列挙する問題、グラフの連結度に関する性質検査、家系図列挙問題などについて効率的なアルゴリズムを与えた.また、一部の問題については、そのアルゴリズムの効率が、ある意味で限界値であることも示した., 18500012
研究期間 2006年 - 2008年

新世代の計算限界-その解明と打破-
岩間 一雄; 伊藤 大雄; 加藤 直樹; 徳山 豪; 田中 圭介; 櫻井 幸一; 浅野 孝夫; 浅野 哲夫; 平田 富夫
日本学術振興会, 科学研究費助成事業, 京都大学, 特定領域研究, 近年のIT社会の大規模化と多様化によって, 従来は計算機があまり入り込まなかった分野においても, アルゴリズムが重要となってきている. また, 例えば配送計画問題をとっても, 配送コストのみではなく, 配送者の負荷の均質化や環境問題への配慮といった, 従来の評価尺度ではとらえきれない観点からの社会的要請があがっている. 本領域ではこうした状況に対処するため, 社会に役立つアルゴリズムをテーマに, 社会的評価基準のもとで数学的に保証されたアルゴリズムの開発・評価の体系化を目指している. 本領域の研究活動は平成19年度で終了した. すでに多くの研究成果が出されており, それらの多くは本領域の設定した目標を順調に達成するものである. 得られた成果をまとめ効果的に公表するため, 総括班のみ平成20年度も活動を行った. 具体的な活動は以下の通りである. (1) 成果報告書の作成 : 総括班および研究課題別の成果をまとめた報告書を作成した. 本特定で開催した研究集会の資料も, とりまとめて記載した. (2) 教科書の出版 : 本領域の分野の教科書を出版する(全16巻). 共立出版より6巻が刊行済みであり, 新たに1巻を刊行した. (3) ニュースレターの発行 : 本領域の最新情報を掲載したニュースレターを発行する. (4) ウェブサイト : 本領域の活動内容の広報として立ち上げた, ウェブサイト(http://keisan-genkai.lab2.kuis.kyoto-u.ac.jp/)の充実をはかった., 16092101
研究期間 2004年 - 2008年

ネットワーク問題のモデル化とアルゴリズムの研究
伊藤 大雄; 岩間 一雄; 増澤 利光; 宮崎 修一; 堀山 貴史
日本学術振興会, 科学研究費助成事業, 京都大学, 特定領域研究, グラフは接続関係を表現する抽象モデルとして有用であり, 古くから盛んに研究されている数学的対象である. 本特定領域研究では, ネットワークや計算機上での問題をグラフ問題としてモデル化し, そのアルゴリズム開発の研究を行った. その結果、密な部分グラフ発見問題, 供給点配置問題, 頂点被覆問題, 巡回セールスマン問題, 自己安定化問題, 安定マッチング問題などの様々な実用的問題について, 効率的なアルゴリズムを得ることができた., 16092215
研究期間 2004年 - 2007年

工学的評価基準に基づく離散アルゴリズムの品質保証技術に関する研究
岩間 一雄; 伊藤 大雄; 宮崎 修一; 堀山 貴史
日本学術振興会, 科学研究費助成事業, 京都大学, 基盤研究(B), 離散アルゴリズムの評価基準は、漸近的な計算時間がほとんど唯一のものとされてきた。しかし、これは評価尺として適切でない場合もしばしば指摘され、様々な角度からアルゴリズムを評価する動きが高まってきた。たとえば、困難な組合せ問題を近似アルゴリズムで解く時の近似度や、将来の入力が分からないオンライン問題に対するアルゴリズムの良さをオフラインアルゴリズムの性能との比較で議論する競合比は、現在最も重要視されている尺度である。本研究では、このような新しい各種尺度を、「工学的評価基準」としてとらえ、そのもとで高性能なアルゴリズムを開発する。ネットワークアルゴリズム、マッチングアルゴリズム、SATアルゴリズムの観点から研究を進めた。以下、代表低な成果である安定結婚問題と頂点被覆問題について述べる。 安定結婚問題の拡張として、希望リストに同順位と不完全指定を許した問題においては最大サイズの安定マッチングを求める問題はNP困難であることが知られている。この問題では、2-近似アルゴリズムは自明である。これまで知られている最良の近似度は2-c/$\sqrt{n}$であったが、我々は初めて2よりも厳密によい近似度である1.8-近似アルゴリズムを達成した。 NP困難問題の一つである頂点被覆問題(VC)が2-ε近似可能か否かは極めて重要性の高い未解決問題であり、その近似不可能性が強く信じられている。我々は密なグラフ上のVCを考え、近似度2を大きく下回る2/(1+Δ/d)の近似アルゴリズムを開発した。ここで、Δはグラフの最大次数、dは平均次数を表す。もしもより良い近似率を達成する結果が存在するならば、一般のVCにおいて2-εの近似度が得られるため、我々の結果が最適である。, 16300002
研究期間 2004年 - 2006年

インターネット問題のモデル化法と効率的算法の研究
伊藤 大雄; 岩間 一雄
日本学術振興会, 科学研究費助成事業, 京都大学, 基盤研究(C), 1.供給点配置問題:グラフG=(V,E)に対し、節点部分集合Sで、与えられたサイズp以下で、カバーする(Sとの間の連結度が所望の値kになっている)節点xの数(あるいは重み和)を最大にするようなSを求める問題を我々は提案し、最大被覆供給点配置問題と呼ぶ。本問題は、インターネット上でミラーサーバーを効率良く配置する問題が定式化されるため、応用上もたいへん重要な問題である。本年度は主にグラフが無向で、連結度が枝連結度である場合を対象とし、以下の結果を得た(ただしGの節点数をn、枝数をmとする)。(1)kが2以下である場合の0(np+m+nlogn)時間算法、(2)Gがk-1枝連結である場合の0(nm+n^2logn)時間算法、(3)Gの形状が木である場合の0(knp^2)時間算法。 2.孤立した密な部分グラフの列挙:グラフから密な部分グラフを見つけ出す問題は、インターネット検索アルゴリズムとの関係で近年注目を浴びている。しかしそのほとんどはNP困難、あるいは解が指数個存在するなど、非常に難しい問題と認識されている。しかし実用上必要なのは、その部分グラフが密であるだけでなく外部との連結が疎でもあるというということに我々は着目し、「孤立部分グラフ」という概念を提唱した。正の数cについて、k節点からなる部分グラフがc-孤立であるとは、外部への枝数がck未満であることを言う。我々は与えられたグラフから全ての極大c-孤立クリーク(クリーク=部分グラフで全節点間に枝があるもの)を列挙する0(c^52^{2c}m)時間アルゴリズムを得た。, 16500010
研究期間 2004年 - 2005年

グラフ・ネットワーク・離散幾何学におけるアルゴリズムの研究
伊藤 大雄; 岩間 一雄
日本学術振興会, 科学研究費助成事業, 京都大学, 基盤研究(C), 1.供給点配置問題 供給点配置問題は、インターネットにおけるミラーサーバ配置問題に応用できる基本的問題である。本研究では、入力が有向グラフG=(V, E)で、両方向の流れに対応する制約条件λ(S, x)≧kとλ(x, S)≧hがあるような供給点配置問題に対し、kとhが定数である場合に多項式時間で動作するアルゴリズムを得た。 2.設備故障に強いインターネットルーチング方式 インターネットにおいて、設備故障などがおきた場合にネットワーク情報の変化を全網に通知して通信経路を変更するが、情報伝達の遅延の影響で、パケットがループに陥ってしまうという「ルーチングループ問題」がおきることが知られている。これを回避するために、ネットワークリソースの変化情報を段階的に流す手法を提案し、最適アルゴリズムを得た。また、リンク故障時の迂回方式として、各ノード毎に迂回テーブルを一つ用意するだけで、かつパケットのヘッダに1ビット加えるだけで実行できる方法を提案した。 3.ファイル転送木問題 与えられたグラフG=(V, E)の各節点x∈Vに対して出次数の上限値d(x)が与えられ、その制約の下での最短路木を求める問題に対し多項式時間アルゴリズムを得た。本問題は、通信ネットワークにおいてファイルを転送する際の適切な経路を計算する問題などに応用を持つ。さらに、出次数制限や最短路性などの制約を緩和した種々の問題について、多項式時間アルゴリズムを与えるか、さもなけれな計算困難であることを証明した。 4.ハイパーグラフの凸多角形上への描画 ハイパーグラフを平面上に描画した時の、各ハイパーエッジの作る面積の和と、凸3カットとの間に成立する、同値な関係を明らかにした。, 14580373
研究期間 2002年 - 2003年

工学的評価基準による離散アルゴリズムの高品質化に関する研究
岩間 一雄; 宮崎 修一; 伊藤 大雄; 岡部 寿男; 堀山 貴史
日本学術振興会, 科学研究費助成事業, 京都大学, 基盤研究(B), 離散アルゴリズムの良さの評価基準として、長期間に渡って、漸近的な計算時間がほとんど唯一のものとされてきた。しかし、この漸近的計算時間が評価尺度として適切でない場合が多いこともしばしば指摘され、様々な角度からアルゴリズムを評価する動きが高まってきた。たとえば、困難な組合せ問題を近似アルゴリズムで解く時の近似率や、将来の入力が分からないオンライン問題を解く時の競合比などである。我々は、このような新しい各種尺度を「工学的評価基準」としてとらえ、この視点のもとで高性能なアルゴリズムを開発する方法論について研究を行った。 結婚安定問題は多項式時間で解くことができると知られていたが、これを一般化し、希望リストに同順位を許した場合や希望リストを完全に指定しない場合にも多項式時間アルゴリズムを示した。同順位と不完全指定を同時に許した場合にはNP困難となるが、この場合に自明な近似率2を切る初めてのアルゴリズムを示した。 充足可能性問題では、局所探索系とバックトラック系の2つのアルゴリズムを相補的に組み合わせることにより、3-SATを1.324^n時間で解くアルゴリズムを構築した。また、与えられた論理式の充足可能性を保存したまま解の密度を濃縮した論理式を求める、論理式の濃縮問題に取り組んだ。 他に、オンラインアルゴリズム、ネットワークアルゴリズム、量子アルゴリズムの各テーマにおいて、アルゴリズムの高品質化に取り組んだ。, 13480081
研究期間 2001年 - 2003年

グラフ・ネットワーク構造を持つ離散最適化問題の定式化とその効率的解法の研究
増山 繁; 巳波 弘佳; 市川 周一; 伊藤 大雄
日本学術振興会, 科学研究費助成事業, 豊橋技術科学大学, 特定領域研究(B), インターネット,マルチメディアネットワーク,移動体通信等の急激な普及にみられるような,近年における計算機や,情報通信技術の高度化に起因して新たに出現してきた問題の多くは,離散的構造を持つ.そこで,我々のグループでは,それらの問題に対して,グラフ・ネットワーク問題によるモデル化を行ない,その構造的な特徴を解明することによって,効率の良い解法を求めてきた. その結果,高度情報通信網,及び,その信頼性に関して,ある種のグラフ上のハミルトン閉路問題,2本の辺素な路問題,故障すると中継数が増大する端末を求める問題,また,高度情報通信網のモデル化とサーバーミラー配置,及び,移動体通信システムにおいて基地局への担当領域の割り当てに関連した問題等について成果を得た. また,未解決であったハムサンドイッチ定理の一般化等,離散幾何学,及び,一般化詰将棋問題等の離散構造を有するゲーム・パズルの計算複雑さに関して共に成果を得た.更に,離散最適化手法を用いた並列,ないし,分散負荷分散問題の解法,及び,専用計算回路の部分グラフ同型問題等の計算困難問題への適用についても実用上有用な成果を得た. 高度情報通信網上で提供されている大量の情報の活用を支援するための基礎技術として重要な情報検索,および,テキスト自動要約とその周辺の研究もTVニュース字幕生成のための要約,複数記事の要約,更には,要約に必要な換言知識の自動獲得,及び,それらのための基礎技術である構文解析等について成果を得た., 10205210
研究期間 1998年 - 2000年