Researcher Profile and Settings

Affiliation

• ＜Faculty / Graduate School / Others＞

  Graduate School of Engineering / Department of Electrical and Electronic Engineering

• ＜Related Faculty / Graduate School / Others＞

  Faculty of Engineering / Department of Electrical and Electronic Engineering

Teaching

• Faculty of Engineering / Department of Electrical and Electronic Engineering, 2022, Data Structures and Algorithms I

  Link to Kobe Univ. syllabus
• Faculty of Engineering / Department of Electrical and Electronic Engineering, 2022, Electrical and Electronics Engineering Laboratory ⅢA

  Link to Kobe Univ. syllabus
• Faculty of Engineering / Department of Electrical and Electronic Engineering, 2022, Electrical and Electronics Engineering Laboratory Ⅲ

  Link to Kobe Univ. syllabus
• Faculty of Engineering / Department of Electrical and Electronic Engineering, 2022, Data Structures and Algorithms ⅡA

  Link to Kobe Univ. syllabus
• Faculty of Engineering / Department of Electrical and Electronic Engineering, 2022, Data Structures and Algorithms Ⅱ

  Link to Kobe Univ. syllabus
• Faculty of Engineering / Department of Electrical and Electronic Engineering, 2022, Electrical and Electronics Engineering Laboratory ⅢB

  Link to Kobe Univ. syllabus
• Faculty of Engineering / Department of Electrical and Electronic Engineering, 2022, Data Structures and Algorithms ⅡB

  Link to Kobe Univ. syllabus
• Graduate School of Engineering / Department of Electrical and Electronic Engineering, 2022, Special Lecture II

  Link to Kobe Univ. syllabus
• Graduate School of Engineering / Department of Electrical and Electronic Engineering, 2022, Computational Complexity Theory

  Link to Kobe Univ. syllabus
• Graduate School of Engineering / Department of Electrical and Electronic Engineering, 2022, Design of Algorithms

  Link to Kobe Univ. syllabus

Research Activities

Research Interests

• data structure
• algorithm
• computer science

Research Areas

• Informatics / Software
• Informatics / Information theory

Published Papers

• Efficient Algorithms for the Ensemble Computation Problem

  Yujiro Ikenaga, Kazuaki Yamaguchi

  Corresponding, IEEE, 24 Nov. 2022, 2022 7th International Conference on Intelligent Informatics and Biomedical Science (ICIIBMS), 235 - 240

  [Refereed]

  International conference proceedings

• Independent Sets Extraction Graph Coloring Algorithm Using Beam Search.

  Kentaro Akashi, Kazuaki Yamaguchi

  2022, SNPD, 230 - 234

  International conference proceedings

• A Greedy Algorithm for the Graph Coloring Problem Using Extraction of Weighted Cliques

  UMEMOTO Soma, YAMAGUCHI Kazuaki

  The graph coloring problem is an important problem. Heuristics like greedy algorithms are often used for graph coloring problem, because it is not practical to apply exact solutions to large graphs. In this paper, we propose two greedy algorithms for the graph coloring problem. The proposed methods weight the vertices or edges of the complement of the input graph, and then extract the weighted clique of the graph. The solution is obtained by repeating this process until no vertices are left. Experimental results show that our methods are more suitable for graphs with high edge density than the previous methods.

  Corresponding, The Institute of Electronics, Information and Communication Engineers, 01 Dec. 2021, 電子電子情報通信学会論文誌A 基礎・境界, J104-A (12), 258 - 266, Japanese

  [Refereed]

• Parallelization of a branch-and-bound algorithm for the maximum weight clique problem

  Satoshi Shimizu, Kazuaki Yamaguchi, Sumio Masuda

  In this paper, parallelization techniques are proposed for the branch-and-bound algorithm OTClique for the maximum weight clique problem. OTClique consists of the precomputation phase and the branch-and-bound phase. The proposed algorithm parallelizes both of them. In the precomputation phase, the construction of optimal tables is parallelized. In the branch-and-bound phase, the proposed algorithm generates small subproblems and assigns them to threads. A technique to share lower and upper bounds is also proposed. Experiments using some benchmarks show that the proposed parallelization techniques improve the performance of OTClique. With an 8-core CPU, the computation time of OTClique becomes 6.91 times shorter on random graphs and 5.38 times on DIMACS benchmarks on average. (C) 2021 Elsevier B.V. All rights reserved.

  Corresponding, ELSEVIER, Aug. 2021, DISCRETE OPTIMIZATION, 41, 100646 - 100646, English

  [Refereed]

  Scientific journal

• Mixed Labeling Algorithms Using Slider Models

  MASUDA Sumio, ABE Noboru, YAMAGUCHI Kazuaki

  Given a set S of points in a region D, we consider the problem of placing labels of all the points in S. The label of each point p ∈ S is either placed inside D so as to touch p or placed outside D using a leader line. This style of labeling is called a mixed labeling. In this paper, we use slider models for the label placement inside D, and present exact algorithms for the problem of finding a label placement such that (a) the number of labels inside D is maximized and (b) the total sum of the lengths of leader lines inside D is minimized as the secondary objective.

  The Institute of Electronics, Information and Communication Engineers, 01 Nov. 2020, 電子電子情報通信学会論文誌A 基礎・境界, J103-A (11), 278 - 282, Japanese

  [Refereed]

• A maximum edge-weight clique extraction algorithm based on branch-and-bound

  Satoshi Shimizu, Kazuaki Yamaguchi, Sumio Masuda

  The maximum edge-weight clique problem is to find a clique whose sum of edge-weight is the maximum for a given edge-weighted undirected graph. The problem is NP-hard and some branch-and-bound algorithms have been proposed. In this paper, we propose a new exact algorithm based on branch-and-bound. It assigns edge-weights to vertices and calculates upper bounds using vertex coloring. By some computational experiments, we confirmed our algorithm is faster than previous algorithms.

  Corresponding, Elsevier BV, Aug. 2020, Discrete Optimization, 37, 100583 - 100583, English

  [Refereed]

  Scientific journal

• 地図ラベル配置問題に対する単純な厳密解法

  城戸 直人, 増田澄男, 山口 一章

  Dec. 2019, 電子情報通信学会論文誌 A, J102-A (12), 314 - 319, Japanese

  [Refereed]

  Scientific journal

• An exact algorithm for the arrow placement problem in directed graph drawings

  KIDO NAOTO, YAMAGUCHI KAZUAKI, MASUDA SUMIO

  We consider the problem of placing arrows, which indicate the direction of each edge in directed graph drawings, without making them overlap other arrows, vertices and edges as much as possible. The following two methods have been proposed for this problem. One is an exact algorithm for the case in which the position of each arrow is restricted to some discrete points. The other is a heuristic algorithm for the case in which the arrow is allowed to move continuously on each edge. In this paper, we assume that the arrow positions are not restricted to discrete points and propose an exact algorithm for the problem of finding an arrow placement such that (a) the weighted sum of the numbers of overlaps with edges, vertices and other arrows is minimized and (b) the sum of the distances between the arrows and their edges' terminal vertices is minimized as a secondary objective. The proposed method solves this problem by reducing it to a mixed integer linear programming problem. Since this is an exponential time algorithm, we add a simple procedure as preprocessing to reduce the running time. Experimental results show that the proposed method can find a better arrow placement than the previous methods and the procedure for reducing the running time is effective.

  電子情報通信学会, Nov. 2019, 電子情報通信学会論文誌, E102-A (11), 1481 - 1489, English

  [Refereed]

  Scientific journal

• 有向グラフ描画における矢じり配置問題に対する発見的手法

  KIDO NAOTO, MASUDA SUMIO, YAMAGUCHI KAZUAKI

  Sep. 2018, 電子情報通信学会論文誌, J101-A (9), 246 - 249, Japanese

  [Refereed]

  Scientific journal

• Data Structures for Local Search Algorithms for the Maximum Edge-weight Clique Problem

  SHIMIZU SATOSHI, ISHIHARA RYOTA, YAMAGUCHI KAZUAKI, MASUDA SUMIO

  辺に重みが付与された無向グラフが与えられたとき，重みの和が最大となるクリークを求める問題を最大辺重みクリーク問題という．本稿ではこの問題に対する局所探索法において近傍を管理するためのデータ構造を2つ提案する．計算機実験により2つの局所探索法でデータ構造を比較し，提案法は従来法より性能が良いことを確認した．また，グラフの性質や計算機のメモリに応じて提案するデータ構造を使い分けることで，効率良く探索を行えることを確認した． The maximum edge-weight clique problem is to find the clique of maximum weight for a given edge-weighted undirected graph. In this paper, we propose two data structures to manage neighborhood in local search algorithms. By some computational experiments, we compared our proposal data structures with two local search algorithms and confirmed ours work better than a previous one. By applying proposal data structures properly, we confirmed local search algorithms work efficiently.

  Corresponding, 情報処理学会, 15 Jul. 2018, 情報処理学会論文誌, 59 (7), 1415 - 1424, Japanese

  [Refereed]

  Scientific journal

• A branch-and-bound based exact algorithm for the maximum edge-weight clique problem

  SHIMIZU SATOSHI, YAMAGUCHI KAZUAKI, MASUDA SUMIO

  Corresponding, International Association for Computer and Information Science, Jul. 2018, Proceedings of 5th International Conference on Computational Science/ Intelligence & Applied Informatics, 116 (316), 63 - 68, English

  [Refereed]

  International conference proceedings

• An algorithm for placing edge labels in a graph drawing by simple rules

  YAMAJI TAKUROU, MASUDA SUMIO, ABE NOBORU, YAMAGUCHI KAZUAKI

  電子情報通信学会, Oct. 2017, 電子情報通信学会論文誌, J100-A (10), 363 - 373, Japanese

  [Refereed]

  Scientific journal

• 数理計画問題による最大辺重みクリーク問題の定式化

  清水 悟司, YAMAGUCHI KAZUAKI, MASUDA SUMIO

  Corresponding, Aug. 2017, 電子情報通信学会論文誌, J100-A (8), 313 - 315, Japanese

  [Refereed]

  Scientific journal

• Fast maximum weight clique extraction algorithm: Optimal tables for branch-and-bound

  Satoshi Shimizu, Kazuaki Yamaguchi, Toshiki Saitoh, Sumio Masuda

  A new branch-and-bound algorithm for the maximum weight clique problem is proposed. The proposed algorithm consists of two phases, a precomputation phase and a branch and-bound phase. In the precomputation phase, the weights of maximum weight cliques in many small subgraphs are calculated and stored in optimal tables. In the branch and-bound phase, each problem is divided into smaller subproblems, and unnecessary subproblems are pruned using the optimal tables. We performed experiments with the proposed algorithm and five existing algorithms for several types of graphs. The results indicate that only the proposed algorithm can obtain exact solutions for all graphs and that it performs much faster than other algorithms for nearly all graphs. (C) 2017 Elsevier B.V. All rights reserved.

  Corresponding, ELSEVIER SCIENCE BV, May 2017, DISCRETE APPLIED MATHEMATICS, 223, 120 - 134, English

  [Refereed]

  Scientific journal

  Link to Kobe Univ. Repository (Kernel)
• 頂点と辺の重なりを削除するグラフレイアウト調整アルゴリズム

  塚本 和樹, MASUDA SUMIO, SAITOH TOSHIKI, YAMAGUCHI KAZUAKI

  Dec. 2016, 電子情報通信学会論文誌, J99-A (12), 471 - 479, Japanese

  [Refereed]

  Scientific journal

• 頂点位置の交換によるグラフ描画の辺交差数削減

  MASUDA SUMIO, FUKUDA SHOTA, YAMAGUCHI KAZUAKI

  Sep. 2016, 電子情報通信学会論文誌, J99-A (9), 387 - 390, Japanese

  [Refereed]

  Scientific journal

• A Fast Heuristic for the Minimum Weight Vertex Cover Problem

  Satoshi Shimizu, Kazuaki Yamaguchi, Toshiki Saitoh, Sumio Masuda

  Given a vertex-weighted undirected graph, to find the vertex cover of minimum weight is called minimum weight vertex cover problem (MWVCP). It is known as an NP-hard problem. In this paper, a fast heuristic for MWVCP is proposed. Our algorithm is based on a simple algorithm called "list-heuristic." Experimenal results show that our algorithm calculates better solutions in shorter time than approximation algorithms for MWVCP.

  Corresponding, IEEE COMPUTER SOC, Jun. 2016, 2016 IEEE/ACIS 15TH INTERNATIONAL CONFERENCE ON COMPUTER AND INFORMATION SCIENCE (ICIS), 341 - 345, English

  [Refereed]

  International conference proceedings

• 階層グラフ描画における道の移動処理を用いた頂点順序決定法

  的場 郁典, MASUDA SUMIO, 荒木 徹也, SAITOH TOSHIKI, YAMAGUCHI KAZUAKI

  Jan. 2015, 電子情報通信学会論文誌, J98-A (1), 152 - 164, Japanese

  [Refereed]

  Scientific journal

• Exact Algorithms for B-Bandwidth Problem with Restricted B

  Hiroshi Yukumoto, SAITOH TOSHIKI, YAMAGUCHI KAZUAKI, MASUDA SUMIO

  The B-BANDWIDTH problem is a decision problem whether the bandwidth of a given graph is smaller than B, and it is NP-complete even if the graph is a small graph class of trees. Cygan and Pilipczuk proposed exponential time and space algorithms for B-BANDWIDTH with n/3 ≤ B where n is the number of vertices. In this paper, we propose two algorithms for the B-BANDWIDTH problem with n/4 ≤ B < n/3. These algorithms are extension of Cygan and Pilipczuk algorithms with restricted B. One of the algorithms takes O∗(4.5n) time and O∗(1.5n) space when n/4 ≤ B < n / 2 log2 1.5, and the other takes O∗(4.77n) time and O∗(1.59n) space when n / 2 log2 1.5 ≤ B < n/3. Our algorithms are fastest O∗(2n) space algorithms for n/4 ≤B < n/3. The 17th Korea-Japan Joint Workshop on Algorithms and Computation, July 13-15, 2014, Okinawa, Japan

  WAAC, Jul. 2014, In Proceedings of the KOREA-JAPAN Joint Workshop on Algorithms and Computation, (2014), 44 - 49, English

  [Refereed]

  International conference proceedings

• An algorithm for the map labeling problem with two kinds of priorities

  Noboru Abe, Yoshinori Amai, Toshinori Nakatake, Sumio Masuda, Kazuaki Yamaguchi

  Apr. 2014, International Journal of Computer and Information Engineering, 8 (5), 802 - 805, English

  [Refereed]

  Scientific journal

• 双方向グラフの最大重み最小帰還辺集合問題について

  ARAKI Tetsuya, MASUDA SUMIO, SAITOH TOSHIKI, YAMAGUCHI KAZUAKI

  神戸大学大学院工学研究科・システム情報学研究科, Mar. 2014, 神戸大学大学院工学研究科・システム情報学研究科紀要, 5 (5), 59 - 64, Japanese

  [Refereed]

  Research institution

  Link to Kobe Univ. Repository (Kernel)
• An Algorithm for Finding an Orthogonal Drawing of a Hierarchical Graph

  ARAKI Tetsuya, MASUDA Sumio, MATOBA Ikunori, YAMAGUCHI Kazuaki, SAITOH Toshiki

  本論文では,階層グラフの直交描画を求めるアルゴリズムを示す.ここで直交描画とは,各辺を垂直・水平線分からなる経路として描いたグラフ描画である.本論文では,与えられた階層グラフの辺集合から高階辺の集合を作成する方法,及びそれらの高階辺を描画する方法を提案する.後者の方法は,各高階辺の描画に2本の水平線分を用い得るものとして,辺交差数と水平線分が占めるy座標の個数をともに少なく抑えながら,直交描画を求めるものである.提案手法の有効性は計算機実験により示す.

  一般社団法人電子情報通信学会, Mar. 2014, 電子情報通信学会論文誌. A, 基礎・境界, 97 (3), 178 - 196, Japanese

  [Refereed]

• 辺交差数が少ない階層グラフ描画作成のためのダミー頂点共有処理

  堀尾 明久, MASUDA SUMIO, 荒木 徹也, SAITOH TOSHIKI, YAMAGUCHI KAZUAKI

  Nov. 2014, 電子情報通信学会論文誌, J97-A (11), 704 - 707, Japanese

  [Refereed]

  Scientific journal

• Optimal table method for finding the maximum weight clique

  SHIMIZU Satoshi, YAMAGUCHI KAZUAKI, MASUDA SUMIO, SAITOH TOSHIKI

  Corresponding, World Scientific and Engineering Academy and Society, Apr. 2013, Proc. of 13th WSEAS International Conf. on Applied ComputerScience, 84 - 90, English

  [Refereed]

  International conference proceedings

• Some improvements on Kumlander's maximum weight clique extraction algorithm

  SHIMIZU SATOSHI, YAMAGUCHI KAZUAKI, SAITOH TOSHIKI, MASUDA SUMIO

  Corresponding, World Academy of Science, Engineering and Technology, Dec. 2012, Proc. International Conf. on Electrical, Computer, Electronics and Communication Engineering, 307 - 311, English

  [Refereed]

  International conference proceedings

• A Labeling Algorithm That Permits Writing Characters from Top to Bottom or in Two Lines

  ABE Noboru, KAWABATA Daiki, MASUDA Sumio, YAMAGUCHI Kazuaki

  平面上に与えられた多数の点に名称などを示す文字列(ラベル)を付けるものとする.本研究では,文字列の縦書きと2行への折返しを許すものとして,多くの点にラベルを配置するアルゴリズムを提案する.提案手法は,各点に対しラベル配置位置の候補(ラベル候補)を定め,それらの中から最終的なラベル位置を決定するものであり,各点のラベル候補の個数を少なく抑えるための工夫をしている.

  一般社団法人電子情報通信学会, 01 Nov. 2012, 電子情報通信学会論文誌. A, 基礎・境界 = The transactions of the Institute of Electronics, Information and Communication Engineers. A, 95 (11), 790 - 793, Japanese

  [Refereed]

• An Algorithm for Finding a Graph Drawing with All Vertex Labels

  ABE Noboru, MASUDA Sumio, YAMAGUCHI Kazuaki

  Gを任意の連結無向グラフとし,その各頂点があらかじめ指定されたサイズのラベルをもつものとする.本論文ではまず,Gのある描画が与えられたときに,その描画中にラベルを配置する新しいアルゴリズムを提案する.この方法は,ラベルが対応する頂点と重なることを許しており,多くのラベルを配置することができる.本論文では次に,グラフGに対して,全頂点のラベルを配置した描画を求めるアルゴリズムを提案する.この方法は,各頂点を比較的小さなサイズの軸平行長方形で表すようなグラフ描画アルゴリズムとして用いることができる.これらの提案手法の有効性は計算機実験により示す.

  一般社団法人電子情報通信学会, 01 Aug. 2012, 電子情報通信学会論文誌. A, 基礎・境界 = The transactions of the Institute of Electronics, Information and Communication Engineers. A, 95 (8), 669 - 682, Japanese

  [Refereed]

  Scientific journal

• An Algorithm for Determining the Vertex Coordinates in a Hierarchical Graph Drawing

  ARAKI Tetsuya, MASUDA Sumio, YAMAGUCHI Kazuaki, MURATA Syouta

  各階層上の頂点の配置順序が指定された階層グラフを描画する際に,頂点の座標を決定する新しいアルゴリズムを提案する.提案法は,描画中の重み付き辺長の2乗の総和を小さくすることを目的としており,グラフの各階層を順に見ていき,それぞれの頂点の配置を動的計画法を用いて求めるものである.従来法の一つである優先度法との比較実験を行ったところ,提案法は,三つの評価基準に関して,より優れた描画を求めることができた.

  一般社団法人電子情報通信学会, 01 Dec. 2011, 電子情報通信学会論文誌. A, 基礎・境界 = The transactions of the Institute of Electronics, Information and Communication Engineers. A, vol.J94-A (12), 960 - 973, Japanese

  [Refereed]

  Scientific journal

• Sharing of Dummy Vertices in a Hierarchical Graph Drawing

  ARAKI Tetsuya, MASUDA Sumio, YAMAGUCHI Kazuaki

  グラフの階層描画において,連続しない階層上の頂点を結ぶ辺の上にはダミー頂点が設けられる.本論文では,まず,ダミー頂点を複数の辺に共有させる単純なアルゴリズムを提案し,計算機実験により,それがグラフを簡潔なものにするために有効であることを示す.ダミー頂点の共有を許す場合,処理後のグラフの頂点数や辺の本数をできるだけ少なくすることが望まれる.本研究では,問題の入力を連結3階層グラフに限定した場合でも,頂点数を最小化する問題及び辺数を最小化する問題がNP困難であることを示す.

  一般社団法人電子情報通信学会, 01 Dec. 2011, 電子情報通信学会論文誌. A, 基礎・境界 = The transactions of the Institute of Electronics, Information and Communication Engineers. A, 94 (12), 950 - 959, Japanese

  [Refereed]

  Scientific journal

• An Algorithm for Placing Labels of the Points and Chains on a Map

  Noboru Abe, Masahiko Kusaki, Sumio Masuda, Kazuaki Yamaguchi

  Apr. 2011, 4 (2), 79 - 99, English

  [Refereed]

  Scientific journal

• An Algorithm for Embedding a Graph Drawing onto an Orthogonal Grid and Its Application to the Production of Deformed Railway Maps

  TACHIBANA Kazuyuki, MASUDA Sumio, YAMAGUCHI Kazuaki, SUZUKI Tomotaka

  各頂点の次数が4以下の任意の単純な無向グラフをGとする.本論文では,グラフ描画アルゴリズムをデフォルメ路線図作成に応用することを念頭において,Gの直線描画Gが与えられたときに,Gの直交描画を求めるアルゴリズムを提案する.提案手法による描画は,Gにおける頂点の相対的位置関係(頂点の座標の大小関係)を基本的に保存しており,各辺の折れ曲がり回数がたかだか4となるものである.本論文では次に,Gの直交描画に対し,道の形状を単純化するためのいくつかの処理を示す.最後に,提案手法とこれらの処理を用いて作成したデフォルメ路線図の例を示す.

  一般社団法人電子情報通信学会, 01 Mar. 2011, 電子情報通信学会論文誌. A, 基礎・境界 = The transactions of the Institute of Electronics, Information and Communication Engineers. A, 94 (3), 180 - 191, Japanese

  [Refereed]

  Scientific journal

• A Rule-Based Labeling Algorithm that Maintains Labeling Spaces

  ISOMURA Yosuke, MASUDA Sumio, YAMAGUCHI Kazuaki

  平面上に与えられた多数の点に対し,名称などを表す文字列(ラベル)をできるだけ多く配置する問題について考える.本研究では,スライダーモデルとルール処理を組み合わせたラベル配置アルゴリズムを提案する.提案手法は,スライダーモデルで用いるラベル配置可能領域をルール処理で縮小あるいは削除していき,ラベル位置を決定するものである.提案手法が従来手法より高いラベル配置率を実現できることを,計算機実験によって示す.

  一般社団法人電子情報通信学会, 01 Oct. 2009, 電子情報通信学会論文誌. A, 基礎・境界 = The transactions of the Institute of Electronics, Information and Communication Engineers. A, 92 (10), 699 - 704, Japanese

  [Refereed]

  Scientific journal

• Improvements on the Cycle Removal Step of a Drawing Algorithm for Directed Graphs

  TERAMOTO Masayuki, MASUDA Sumio, YAMAGUCHI Kazuaki

  有向グラフに対する代表的な描画アルゴリズムとして,階層的描画を求めるSugiyamaらの方法が知られている.この方法の第1段階はグラフの非閉路化を行うが,その際,帰還辺の本数を少なくすることを目標としている.本研究では,従来の方法を改良し,帰還辺の本数だけでなく,描画の階層数の削減にも有効な発見的アルゴリズムを提案する.

  一般社団法人電子情報通信学会, 01 Jun. 2009, 電子情報通信学会論文誌. A, 基礎・境界 = The transactions of the Institute of Electronics, Information and Communication Engineers. A, 92 (6), 434 - 439, Japanese

  [Refereed]

  Scientific journal

• A Local Search Algorithm for Reducing Edge Crossings in a Hierarchical Graph Drawing

  TAMORI Kentaro, YAMAGUCHI Kazuaki, MASUDA Sumio

  階層的グラフの描画において,辺の交差が少なくなるように各階層上の頂点の順序を決定する問題について,多くの研究が行われており,有効な発見的手法として重心法が知られている.本論文では,重心法を用いて得られた頂点順序に対し,局所探索法によって辺交差数を更に削減する方法を提案する.また,頂点が階層以外にもグループ分けされており,各階層で同一グループの頂点を連続して並べるものとした場合について考え,そのような場合に適用できるよう,重心法と局所探索法による方法を拡張する.

  Corresponding, 一般社団法人電子情報通信学会, 01 Jan. 2009, 電子情報通信学会論文誌. A, 基礎・境界 = The transactions of the Institute of Electronics, Information and Communication Engineers. A, 92 (1), 55 - 61, Japanese

  [Refereed]

  Scientific journal

• An Algorithm for a Generalized Label Size Maximization Problem

  NISHIYAMA Takeshi, YAMAGUCHI Kazuaki, MASUDA Sumio

  平面上の複数の点に対して,名称などを表す文字列(ラベル)を配置することを考える.本研究では,ラベルサイズ最大化問題の一つの一般化として,達成すべきラベル配置率Pが指定されたときに,配置率がP以上になるラベル配置で,ラベルサイズができるだけ大きいものを求めるという問題を扱う.本論文ではまず,ラベル数最大化問題に対するWagnerらの方法を繰り返し実行することにより,上記の問題の解を求める単純な発見的アルゴリズムを示す.そして,いくつかの工夫を加えることにより,その実行時間と解の精度を改善する方法を提案し,計算核実験によってその効果を確認する.

  Corresponding, 一般社団法人電子情報通信学会, 01 Dec. 2008, 電子情報通信学会論文誌. A, 基礎・境界 = The transactions of the Institute of Electronics, Information and Communication Engineers. A, 91 (12), 1223 - 1228, Japanese

  [Refereed]

  Scientific journal

• Improvements on the Method for Moving Vertices in a Force-Directed Graph Drawing Algorithm

  UEDA Kohei, MASUDA Sumio, YAMAGUCHI Kazuaki

  無向グラフを対象とした描画法の一つとして,川西らの方法が知られている.この方法は,いくつかの評価基準に関して,他の代表的な力指向描画法より優れた描画を得るものであるが,(i)最終的な描画が頂点の処理順序に依存し,その順序によっては不適切な描画になることがある,(ii)対応できるグラフのサイズが狭い範囲に限られている,という問題をもつ.本論文では,川西らの方法の頂点移動方法を改良することによって新しい描画法を提案し,その有効性を計算機実験により示す.

  一般社団法人電子情報通信学会, 01 Oct. 2008, 電子情報通信学会論文誌. A, 基礎・境界 = The transactions of the Institute of Electronics, Information and Communication Engineers. A, 91 (10), 974 - 982, Japanese

  [Refereed]

  Scientific journal

• A New Exact Algorithm for the Maximum Weight Clique Problem

  YAMAGUCHI Kazuaki, MASUDA Sumio

  Given an undirected graph with weight for each vertex, the maximum weight clique problem is to find the clique of the maximum weight. Ostergard proposed a fast exact algorithm for solving this problem. We show his algorithm is not efficient for very dense graphs. We propose an exact algorithm for the problem, which is faster than Ostergard's algorithm in case the graph is dense. We show the efficiency of our algorithm with some experimental results.

  The Institute of Electronics, Information and Communication Engineers, Jul. 2008, Proceedings of the 23rd International Technical Conference on Circuits/Systems, Computers and Communications, pp.317-320, F3-1, English

  [Refereed]

  International conference proceedings

• An exact algorithm for the maximum weight K(3)-free subgraph problem

  Masayasu Fujiwara, Kazuaki Yamaguchi, Sumio Masuda

  The maximum independent set problem is one of the most famous and well-studied NP-complete problems, and has some important applications. Some exact algorithms based on the branch-and-bound technique have been proposed for the problem. This paper deals with one of its variants, the maximum weight K(3)-free subgraph problem. This paper shows an interesting property of a K(3)-free graph, an exact algorithm for the problem and its efficiency with some computer experiments.

  Corresponding, INT ASSOC ENGINEERS-IAENG, 2008, WORLD CONGRESS ON ENGINEERING 2008, VOLS I-II, Vol II, pp.834-837, 834 - 837, English

  [Refereed]

  International conference proceedings

• On the Special Issue of "The 2006 Kansai Section Joint Convention of Institutes of Electrical Engineering Japan"

  YAMAGUCHI Kazuaki

  01 Nov. 2007, 電気学会論文誌. C, 電子・情報・システム部門誌 = The transactions of the Institute of Electrical Engineers of Japan. C, A publication of Electronics, Information and System Society, 127 (11), 1821, Japanese

• A Data Structure for Geographic Region Data Using a Region Adjacency Graph

  KUMANO Tatsuo, YAMAGUCHI Kazuaki, MASUDA Sumio

  空間データを効率的に管理するための索引構造は地理情報システムなどで利用される.本論文では範囲検索の性能を向上させることを目的として,領域データを管理する新たなデータ構造を提案する.このデータ構造は,領域データの隣接関係を表したグラフを用いる.地図における領域データを用いた計算機実験により,提案したデータ構造の範囲検索性能が優れていることを示す.

  Corresponding, 一般社団法人電子情報通信学会, 01 Feb. 2007, 電子情報通信学会論文誌. D, 情報・システム = The IEICE transactions on information and systems (Japanese edition), 90 (2), 586 - 591, Japanese

  [Refereed]

  Scientific journal

• An Approximation k Nearest Neighbour Search Algorithm Based on TLAESA

  Ken TOKORO, Kazuaki YAMAGUCHI, Sumio MASUDA

  高速な最近傍検索手法の一つとしてTLAESAが知られている.本論文では更なる高速化を目的として,TLAESAのデータ構造と検索アルゴリズムの改良を行う.更に解の精度を保証できるような近似κ近傍検索手法への拡張を提案する.提案手法は非常に低いエラー率で近似解を求めることができることを計算核実験により示す.

  Corresponding, 一般社団法人電子情報通信学会, Jul. 2006, 電子情報通信学会論文誌, vol.J89-D, no.7, pp.1610-1616 (7), 1610 - 1616, Japanese

  [Refereed]

  Scientific journal

• Label placement with leader lines

  OOMORI Kazuki, MASUDA Sumio, YAMAGUCHI Kazuaki

  平面上の点の集合が与えられたとき,できるだけ多くの点にラベルを付けることを目的としたアルゴリズムが数多く提案されているが,ラベルのサイズが大きい場合などには,ラベルを表示できない点が多数残ることがある.本研究では,そのような場合に,ラベルを表示できなかった点に対し,引出し線を用いてラベルの配置を試みるアルゴリズムを二つ提案し,それらの有効性を計算機実験により示す.

  一般社団法人電子情報通信学会, Mar. 2006, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol.J89-A, no.3, pp.268-275 (3), 268 - 275, Japanese

  [Refereed]

  Scientific journal

• An A* algorithm with a new heuristic distance function for the 2-terminal shortest path problem

  K Yamaguchi, S Masuda

  The 2-terminal shortest path problem is to find a shortest path between two specified vertices in a given graph G. In this paper, we consider this problem in the following situation: G is given before the two vertices are specified so that some preprocessing is allowed to reduce the response time. We present a method for calculating lower bounds of the length of the shortest path for any pair of vertices. Experimental results,show that the A* algorithm with our method performs much better than previous methods.

  IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, Feb. 2006, IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, E89A (2), 544 - 550, English

  [Refereed]

  Scientific journal

• Improvements of TLAESA nearest neighbour search algorithm and extension to approximation search

  TOKORO Ken, YAMAGUCHI Kazuaki, MASUDA Sumio

  Corresponding, Australian Computer Society, Jan. 2006, Proceedings of the 29th Australasian Computer Science Conference, pp.77-83, 77 - 83, English

  [Refereed]

  International conference proceedings

• Algorithms for the map labeling problem with priorities

  FUNAKAWA Kunio, ABE Noboru, MASUDA Sumio, YAMAGUCHI Kazuaki

  優れた地図ラベル配置アルゴリズムの一つとして, Wagner and Wolffによる方法が知られている.本研究では, この方法を拡張することによって, 地点の消去を許さない場合と許す場合の両方について, 地点の優先度を考慮したラベル配置アルゴリズムを提案し, それらの有用性を計算機実験により示す.

  一般社団法人電子情報通信学会, May 2005, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol.88-A, no.5, pp.677-681 (5), 677 - 681, Japanese

  [Refereed]

  Scientific journal

• Experimental evaluation of the algorithms for placing labels in a graph drawing

  ABE Noboru, MASUDA Sumio, YAMAGUCHI Kazuaki

  グラフ描画中に頂点及び辺のラベルを配置する五つのアルゴリズムについて, ラベル配置率及び実行時間に関する比較を行った.計算機実験の結果では, 地図へのラベル配置を目的としたKameda and Imaiの方法に変更を加えたもの, 及び筆者らによる頂点ラベルの配置法と辺ラベルの配置法を組み合わせ, それに改良を加えたものが優れていた.

  一般社団法人電子情報通信学会, May 2005, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol.88-A, no.5, pp.671-676 (5), 671 - 676, Japanese

  [Refereed]

  Scientific journal

• A method to extend an algorithm for the maximum clique problems to an algorithm for the maximum weighted clique problem

  YAMAGUCHI Kazuaki, SAKAKIBARA Yoshie, MASUDA Sumio

  2004, Proc.2004 International Technical Conf.on Circuits/Systems,Computers and Communications, E87-A(10),2774-2779, English

  [Refereed]

  International conference proceedings

• An Algorithm for Drawing Undirected Graphs with Edge Labels

  ABE Noboru, MASUDA Sumio, YAMAGUCHI Kazuaki

  一般社団法人電子情報通信学会, 01 Aug. 2003, IEICE transactions on fundamentals of electronics, communications and computer sciences, 86 (8), 2179 - 2180, English

  [Refereed]

• 辺がラベルをもつ無向グラフの描画法

  阿部 昇, 増田 澄男, 山口 一章

  Gを連結な無向グラフとし,その各辺が,あらかじめ決められたサイズのラベルをもつものとする.辺がラベルをもつ無向グラフの描画法としてこれまで主に検討されてきたアプローチは,まずラベルの情報を特に考慮せずにグラフの頂点と辺を描き,次に適切な位置に辺のラベルを配置するというものであった.しかしこのようなアプローチでは,グラフが密である場合やラベルのサイズが大きい場合に,配置できないラベルが多く残ることがある.そこで本論文では,各辺のラベルの配置位置を考慮しながら頂点や辺の位置を決定するグラフ描画アルゴリズムを提案する.そして,この方法で得られる描画に対してラベル配置アルゴリズムを実行すれば,既存の(ラベルをもたないグラフを描画対象とした)グラフ描画アルゴリズムで得られる描画に対して同じことを行う場合に比べ,ラベル配置率を大幅に改善できることを計算機実験により示す.

  一般社団法人電子情報通信学会, 2003, 電子情報通信学会論文誌, J86-A(8),pp.848-859 (8), 848 - 859, Japanese

  [Refereed]

  Scientific journal

• Placement of vertex labels in a graph drawing

  ABE Noboru, MASUDA Sumio, YAMAGUCHI Kazuaki

  2003, Proc. 3rd Hungarian-Japanese Symp. On Discrete Mathematics and Its Applications, 69-78, English

  [Refereed]

  International conference proceedings

• An algorithm for drawing a Graph with vertex labels.

  ABE Noboru, MASUDA Sumio, YAMAGUCHI Kazuaki

  2003, Proc. 7th Japan-Korea Workshop on Algorithms and Computation., 267-275, English

  [Refereed]

  International conference proceedings

• An Algorithm for Placing Edge Labels in a Graph Drawing

  ABE Noboru, MASUDA Sumio, YAMAGUCHI Kazuaki

  Let G be a graph and Γ be its drawing on a plane. Each edge in G has a label of specified size. We consider the problem of placing edge labels in Γ in such a way that no label overlaps vertices, edges or other labels. Recently, Kakoulis and Tollis proposed a heuristic algorithm for this problem. In this paper, we improve their algorithm by refining the part for deciding the candidates of label positions and that for choosing the final label positions. Experimental results show that our algorithm can place more labels than the original one.

  一般社団法人電子情報通信学会, 01 Mar. 2002, IEICE transactions on fundamentals of electronics, communications and computer sciences, 85 (3), 729, English

  [Refereed]

• グラフ描画における辺のラベルの配置法

  阿部 昇, MASUDA SUMIO, YAMAGUCHI KAZUAKI

  Gをグラフとし,гをGの平面上への描画とする.Gの各辺に対し,あらかじめラベルのサイズが決められているものとする.このとき,どのラベルも頂点や辺及び他のラベルと重ならないようにして,できるだけ多くの辺のラベルをг中に配置するという問題について考察する.最近,Kakoulis and Tollisは,この問題に対し,まず各辺のラベルを配置する位置の候補を複数個定め,次にそれらの中から最終的なラベル位置を選択するというヒューリスティクスを提案した.本研究では,ラベルの配置位置の候補を定める部分やラベル位置を選択する部分にいくつかの工夫をすることにより,この方法の改良を行う.そして,これによってラベル配置率が改善できることを計算機実験により示す.

  一般社団法人電子情報通信学会, Mar. 2002, 電子情報通信学会論文誌, J85-A (3), 306 - 314, Japanese

  [Refereed]

  Scientific journal

• グラフ描画における頂点ラベルの配置法

  菊地 玄人, MASUDA SUMIO, YAMAGUCHI KAZUAKI

  一般社団法人電子情報通信学会, Jan. 2002, 電子情報通信学会論文誌, J85-A (1), 141 - 147, Japanese

  [Refereed]

  Scientific journal

• GBD木における線分の分割法の改良

  伊野 敦士, MASUDA SUMIO, YAMAGUCHI KAZUAKI

  平面上の線分の集合を管理し得るデータ構造の一つとしてGBD木が知られている.GBD木により, 線分の効率的な挿入・削除と範囲検索が可能であるが, 長い線分が存在する場合に検索効率が低下することがある.この問題点に対処するため, 長い線分を複数個に分割することが提案されているが, その方法は非常に単純なものであり, 改善の余地が残されている.本研究では, 線分の新しい分割方法を提案し, GBD木の検索効率が更に改善できることを計算機実験により示す.

  一般社団法人電子情報通信学会, Dec. 2000, 電子情報通信学会論文誌, J83-D-1 (12), 1300 - 1304, Japanese

  [Refereed]

  Scientific journal

• 2種類の理想距離によるEadesのグラフ描画法の改良

  川西 和人, MASUDA SUMIO, YAMAGUCHI KAZUAKI

  代表的な無向グラフ描画法の一つであるEadesのアルゴリズムは, 単純でプログラム化が容易であるという長所をもつが, 描画中に極端に長い辺や, 頂点と辺の近接を生じることがある.これらの問題点を解決するため, 本研究では, Eadesのアルゴリズムに頂点間及び頂点と辺の間の理想距離を導入し, それらに基づく力を定義する.計算機実験を行ったところ, この改良により, 描画中の辺の交差数は若干増加したものの, 辺の長さの一様性, 及び頂点と辺の近接数に関して大きく改善することができた.

  一般社団法人電子情報通信学会, Sep. 2000, 電子情報通信学会論文誌, J83-A (9), 1117 - 1121, Japanese

  [Refereed]

  Scientific journal

• 折れ線や曲線を用いた無向グラフ描画アルゴリズム

  萱原 雅之, MASUDA SUMIO, YAMAGUCHI KAZUAKI

  様々な構造の視覚化を目的として, グラフの自動描画法に関する研究が広く行われている.従来の無向グラフ描画法の多くは, 頂点の位置を決定した後, 辺を直線のみで描く.しかし, これは, 辺と頂点の近接(辺と頂点が近づきすぎる現象)や, 辺の交差を増加させる一つの原因となっている.本論文では, Kamadaらによるアルゴリズムをもとにして, 必要に応じて辺を折れ線や曲線で描く描画法を提案する.更に, 本方法が, 辺と頂点の近接や辺の交差数を減少させ, より構造の理解しやすい描画を得ることを実験的に示す.

  一般社団法人電子情報通信学会, Apr. 2000, 電子情報通信学会論文誌, J83-A (4), 402 - 411, Japanese

  [Refereed]

  Scientific journal

• 2段階の木による領域情報管理構造の構成法

  浜畑 直哉, MASUDA SUMIO, YAMAGUCHI KAZUAKI

  地図のように, 平面上のある範囲が複数の領域に分かれているとき, 個々の領域の位置や形状を示す情報を管理するための方式の一つとして, "2段階の木構造による領域情報管理法式"が知られている.これは, 領域が存在する範囲を2等分割する操作を, 分割された各部分内の領域が1種類になるまで再帰的に行い, その分割過程を2段階の木構造により表すというものである.このデータ構造を用いると, 指定された点を含む領域を求める点検索, 及び指定された面(小さな方形範囲)と共通部分をもつ領域をすべて求める面検索を効率的に行うことができる.本論文では, 2段階の木構造の新しい構成法を三つ提案する.最初の二つの方法は, 領域の角(各領域の周を構成する垂直・水平線分の端点)が存在する座標でのみ分割を行うもので, 従来方法に比べて, 木の節点数を大幅に減少させる.また, 三つ目の方法は, 動的計画法を用いることにより, 点検索時に訪問する節点数の期待値が最小となるように木構造を構成する.

  一般社団法人電子情報通信学会, Jan. 2000, 電子情報通信学会論文誌, J83-D-1 (1), 134 - 142, Japanese

  [Refereed]

  Scientific journal

• MD木の領域分割法の改良

  福島 尚高, YAMAGUCHI KAZUAKI, MASUDA SUMIO

  動的な多次元点データの効率的な管理と高速な範囲検索が可能なデータ構造として, 様々なものが知られている. その中で, MD木は高いメモリ効率と範囲検索効率を示すことが報告されている. しかし, ある座標軸に関してソートされた順序でデータが投入されるとき, MD木の範囲検索効率が低下する場合がある. また, 木の作成時には, メモリ効率の向上を目的として領域の動的調整が頻繁に行われ, 作成時間が長くかかる原因となっている. 本研究では, MD木の領域分割法を改良することにより, 高いメモリ効率を保持したまま, これらの問題点を解決する方法を提案する.

  一般社団法人電子情報通信学会, Mar. 1999, 電子情報通信学会論文誌, J82-D-I (3), 508 - 513, Japanese

  [Refereed]

  Scientific journal

• Shortest Path Problem with an Obstructor

  YAMAGUCHI Kazuaki, ARAKI Toshiro, KASHIWABARA Toshinobu

  出発地,目的地なる2頂点s,tが指定されたグラフG=(V,E),妨害数なる正整数k,各辺の(正の)重みl(・)が与えられている.このとき,2人の競技者P1とP2が以下のルールに従ってゲームを行う. P1はsを出発地点とし,1回に一つの辺をたどって目標地点tまで行こうとする.P2は自分の手番にいくつかの辺を切断する.P2の切断できる辺の数はゲームを通じてk本までとする. P1, P2ともグラフ全体が見えているものとする.P1は自分の通る辺の長さの和(道のり)ができるだけ小さくなるようにし,P2はできるだけ大きくなるようにする.本論文では,2人が最善を尽くしたときの道のりをO(n^(m+nlogn)) (m=|E|, n=|V|)時間で求め得ることを示す.また,2人が最善を尽くしたときの道のりが与えられたある正整数以下であるか否かを判定する問題はすべての辺の長さを1とした場合でもP-SPACE-completeであることを示す.

  Lead, 一般社団法人電子情報通信学会, 25 Nov. 1996, 電子情報通信学会論文誌. A, 基礎・境界, 79 (11), 1866 - 1876, Japanese

  [Refereed]

• Maximum-weight-window problem of a planar graph

  Kazuaki Yamaguchi, Ken Kotani, Sumio Masuda, Toshinobu Kashiwabara

  When a planar graph is drawn, the drawing plane is divided into several regions, each of which is called a face. A subgraph composing the periphery of a face is called a window. For each window W that exists in the drawing of a planar graph G, the total sum of the weights of the vertices and the edges is called the weight of the window W. Among all windows that can appear in drawings, the window with the maximum weight is called the maximum-weight-window of G. This paper considers the problem of determining the drawing with the maximum-weight-window. The result for this problem is already obtained for the case where the graph is 2-connected, as well as for the case where the graph is not necessarily 2-connected but all weights are nonnegative. This paper considers also the arbitrary planar graph with real-valued weights, and shows that the drawing with the maximum-weight-window can be determined in O(n + e) time. This result can be applied to the layout design for LSI and printed board, as well as to the diagram representation of the network. It can also be applied to the solution of the maximal planarization problem for the graph.

  Lead, John Wiley and Sons Inc., 1996, Electronics and Communications in Japan, Part III: Fundamental Electronic Science (English translation of Denshi Tsushin Gakkai Ronbunshi), 79 (8), 86 - 92, English

  [Refereed]

  Scientific journal

• 平面グラフの最大重み窓問題

  YAMAGUCHI KAZUAKI, 小谷 健, MASUDA SUMIO, 柏原 敏伸

  平面グラフの描写は描かれている平面をいくつかの領域に分割しているが,それらの領域のそれぞれを面と呼び,各面の周を構成しているような部分グラフを窓と呼ぶ.平面グラフGの描写中に存在し得る各窓Wについて,その頂点と辺の重みの総和を窓Wの重みと呼ぶ.描写に現れ得るすべての窓のうちで重みが最大のものを,Gの最大重み窓と呼ぶ.本論文では最大重み窓をもつ描写を求める問題について考える.グラフが2連結である場合およびすべての重みが非負であり2連結とは限らない場合についての結果は既に得られていた.本論文では実数の重みの与えられた任意の平面グラフに対して,O(n+e)時間で最大重み窓をもつ描写を求めることができることを示す.この結果はLSIや印刷基板のレイアウト設計,ネットワークの図示などに応用をもち,また,グラフの極大平面化問題を解くことにも用いることができる.

  Lead, 一般社団法人電子情報通信学会, Oct. 1995, 電子情報通信学会論文誌, J78-A (10), 1335 - 1340, Japanese

  [Refereed]

  Scientific journal

• NP-Completeness of Interval Graph Completion from a Path Graph

  YAMAGUCHI Kazuaki, ARAKI Toshiro, KASHIWABARA Toshinobu

  一つの木の上の道の集合が与えられたとき,道に対応して頂点をもち,二つの道が交わるとき対応する頂点が辺で結ばれているようなグラフをパスグラフと呼ぶ.直線上の有限個の区間の集合Aが与えられたとき,Aに属する区間を頂点とし二つの区間が交わるとき間に辺を持つようなグラフを区間グラフと呼ぶ.本研究では,パスグラフにK本以下の本数の辺を付加して区間グラフに変換することができるか否かを判定する問題がNP完全であることを証明する.

  Lead, 一般社団法人電子情報通信学会, 25 Sep. 1994, 電子情報通信学会論文誌. A, 基礎・境界, 77 (9), 1269 - 1275, Japanese

  [Refereed]

MISC

• 最大重みクリーク抽出法における彩色による上界の実験的評価

  柏原 優稀, 山口 一章

  一般社団法人 人工知能学会, 06 Mar. 2023, 人工知能学会研究会資料 人工知能基本問題研究会, 124, 20 - 24, Japanese

• ナーススケジューリング問題に対するペナルティ法の実験的評価

  野中 和樹, 山口 一章

  一般社団法人 人工知能学会, 05 Jan. 2023, 人工知能学会研究会資料 人工知能基本問題研究会, 123, 37 - 42, Japanese

• Improvements to the LDS for the Maximum Weight Clique Problem

  YOUNGJAE Kim, YAMAGUCHI Kazuaki

  The Japanese Society for Artificial Intelligence, 15 Mar. 2022, JSAI Technical Report, SIG-FPAI, 120, 36 - 41, Japanese

• The Improvement of RLF for the Vertex Coloring Problem

  KUDOU Iori, YAMAGUCHI Kazuaki

  The Japanese Society for Artificial Intelligence, 15 Mar. 2022, JSAI Technical Report, SIG-FPAI, 120, 18, Japanese

• Proposal of Greedy Random Method for Ensemble Computation

  IKENAGA Yujiro, YAMAGUCHI Kazuaki

  The Japanese Society for Artificial Intelligence, 15 Mar. 2022, JSAI Technical Report, SIG-FPAI, 120, 07, Japanese

• 負の重みを許した最大重みクリーク問題に対する厳密解法

  西藤 光, 山口 一章

  最大重みクリーク問題において、負の重みを許した問題はあまり研究されてこなかった。本稿では、頂点と辺に重みのあるグラフにおいて負の重みを許した最大重みクリーク問題に対して、分枝限定法に基づく厳密解法を提案する。

  [情報処理学会関西支部], 10 Sep. 2021, 2021年度 情報処理学会関西支部 支部大会 講演論文集, 2021 (2021), 4p, Japanese

• Efficient local search for the linear ordering problem

  大藤 聖也, 山口 一章

  線形順序付け問題は，辺に重みのついた有向グラフが与えられたときに，できるだけ逆向きの辺が生じないように頂点に順序を付ける問題である．この問題は，局所探索法でよい解が得られることが知られている．本発表では，局所探索に関する効率化を提案する．

  [情報処理学会関西支部], 10 Sep. 2021, 情報処理学会関西支部支部大会講演論文集, 2021 (2021), 4p, Japanese

• 線形配置問題に対する改良型ヒューリスティック

  田中 僚, 山口 一章, 増田 澄男

  13 Sep. 2019, (2019), Japanese

• グラフ彩色問題に対する局所探索法の実験的評価

  大井 智裕, 山口 一章, 増田 澄男

  2019, (2019), 4p, Japanese

• 2階層にまたがる頂点をもつグラフの描画アルゴリズムの改良

  池田 浩一郎, 増田 澄男, 山口 一章

  21 Sep. 2018, (2018), Japanese

• 地図ラベル配置問題に対する厳密解法の提案

  城戸 直人, 増田 澄男, 山口 一章

  21 Sep. 2018, (2018), Japanese

• 最大辺重みクリーク問題に対する分枝限定法に関する一考察

  池田 総志, 山口 一章, 増田 澄男

  21 Sep. 2018, (2018), Japanese

• 整数計画法を用いたデフォルメ路線図改良法

  一ノ瀬 拓海, 多鹿 雄策, 増田 澄男, 斎藤 寿樹, 山口 一章

  16 Sep. 2016, (2016), Japanese

• 最大辺重みクリーク問題に対する局所探索法の実験的評価

  清水 悟司, 石原 諒大, 山口 一章, 増田 澄男

  16 Sep. 2016, (2016), Japanese

• Proposal of a Fast Heuristic for the Minimum Weight Vertex Cover Problem

  清水 悟司, 山口 一章, 斎藤 寿樹, 増田 澄男

  電子情報通信学会, 22 Apr. 2016, 電子情報通信学会技術研究報告 = IEICE technical report : 信学技報, 116 (17), 23 - 28, Japanese

• A study on branch-and-bound heuristics for the maximum weight clique problem

  芝野 悟, 山口 一章, 斎藤 寿樹

  [情報処理学会関西支部], 2015, 情報処理学会関西支部支部大会講演論文集, (2015), 4p, Japanese

• A New Search Strategy in Branch-and-Bound Algorithms

  YAMAGUCHI Kazuaki, SAITOH Toshiki, MASUDA Sumio

  The branch-and-bound method is used in many exact algorithms for optimization problems. In most case, those algorithms are implemented with the depth rst search. Other search strategies are rarely used because they require large storage areas. In this paper, we propose a new search strategy, the widening search. The widening search greedily nds a solution at rst, and then gradually widens the search space. The storage size required by the widening search is almost same as the depth rst search. We implemented the branch-and-bound algorithm for the maximum weight clique problem with the depth rst search and the widening search and compared their performances. Experimental results show that the solutions by the widening search are much better than the solutions by the depth rst search.

  The Japanese Society for Artificial Intelligence, 06 Oct. 2014, JSAI Technical Report, SIG-FPAI, 95, 01, Japanese

• A linear-time heuristic for the weighted vertex cover problem

  田中智之, 山口一章, 斎藤寿樹, 増田澄男

  [情報処理学会関西支部], 10 Sep. 2014, 情報処理学会関西支部支部大会講演論文集, (2014), 6p, Japanese

• 2-G-2 2種類の優先度を考慮したラベル配置アルゴリズム(離散最適化(3))

  阿部 昇, 天井 善規, 中武 俊典, 増田 澄男, 山口 一章

  公益社団法人日本オペレーションズ・リサーチ学会, 06 Mar. 2014, 日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, 2014, 250 - 251, Japanese

• Efficient Enumeration of Directed Binary Perfect Phylogenies using Dynamic Programming

  Kazuki Morito, Toshiki Saitoh, Kazuaki Yamaguchi, Sumio Masuda

  We consider an enumeration of directed binary perfect phylogenies from incomplete data. Recently, Kiyomi et al. proposed an enumeration algorithm for directed binary perfect phylogenies using ZDDs. A ZDD is a compact data structure for a family of sets provided with a rich family of set operations. Kiyomi's algorithm constructs a ZDD which represents all directed binary perfect phylogenies using these operations. On the other hand, Knuth proposed an algorithm for enumerating paths in a graph by using a ZDD. This method is based on a dynamic programming, and construct the objective ZDD, directly. In this paper, we propose an efficient algorithm for enumerating directed binary perfect phylogenies using the dynamic programming. We show an effectivity of our algorithm by computational experiment.

  Information Processing Society of Japan (IPSJ), 10 May 2013, IPSJ SIG Notes, 2013 (10), 1 - 8, Japanese

• Efficient Enumeration of Directed Binary Perfect Phylogenies using Dynamic Programming

  MORITO Kazuki, SAITOH Toshiki, YAMAGUCHI Kazuaki, MASUDA Sumio

  We consider an enumeration of directed binary perfect phylogenies from incomplete data. Recently, Kiyomi et al. proposed an enumeration algorithm for directed binary perfect phylogenies using ZDDs. A ZDD is a compact data structure for a family of sets provided with a rich family of set operations. Kiyomi's algorithm constructs a ZDD which represents all directed binary perfect phylogenies using these operations. On the other hand, Knuth proposed an algorithm for enumerating paths in a graph by using a ZDD. This method is based on a dynamic programming, and construct the objective ZDD, directly. In this paper, we propose an efficient algorithm for enumerating directed binary perfect phylogenies using the dynamic programming. We show an effectivity of our algorithm by computational experiment.

  The Institute of Electronics, Information and Communication Engineers, 10 May 2013, IEICE technical report. Theoretical foundations of Computing, 113 (50), 63 - 70, Japanese

• An Algorithm for Finding an Orthogonal Drawing of a Hierarchical Graph

  ARAKI Tetsuya, MASUDA Sumio, MATOBA Ikunori, YAMAGUCHI Kazuaki, SAITOH Toshiki

  In this article, we show an algorithm for finding an orthogonal drawing of a hierarchical graph. In an orthogonal drawing, each edge is drawn as a path consisting of vertical and horizontal line segments. We present a method for determining the x-coordinates of the vertices so that the total sum of the lengths of horizontal line segments becomes small. We also propose a method for drawing hyperedges. It uses at most two horizontal line segments to draw each hyperedge and can make both the number of edge crossings in the graph drawing and that of y-coordinates of the horizontal line segments small.

  The Institute of Electronics, Information and Communication Engineers, 24 Apr. 2013, IEICE technical report. Theoretical foundations of Computing, 113 (14), 35 - 42, Japanese

• A New Exact Algorithm for the Maximum Weight Clique Problem Based on an Upper Bound Calculated by Dynamic Programming

  SHIMIZU Satoshi, YAMAGUCHI Kazuaki, SAITOH Toshiki, MASUDA Sumio

  Given a vertex-weighted undirected graph, the problem to find the clique of maximum weight is the maximum weight clique problem. We propose a new exact algorithm based on the branch-and-bound. An upper bound of solution is calculated for each subproblem in branch-and-bound algorithms. Our algorithm makes some small subproblems, calculates their upper bounds by dynamic programming, and store the upper bounds to a table. In branch-and-bound, our algorithm calculates an upper bound fast by referring to the table. We confirm our algorithm is faster than other algorithms.

  The Institute of Electronics, Information and Communication Engineers, 18 Mar. 2013, IEICE technical report. Theoretical foundations of Computing, 112 (498), 47 - 53, Japanese

• 階層グラフの直交描画における線分座標決定

  荒木徹也, 増田澄男, 山口一章

  14 Sep. 2012, 平成24年度 情報処理学会関西支部 支部大会 講演論文集, 2012, Japanese

• 最大重みクリーク抽出法における分枝順序の検討

  森中諒太, 清水悟司, 山口一章, 増田澄男

  14 Sep. 2012, 平成24年度 情報処理学会関西支部 支部大会 講演論文集, 2012, Japanese

• ある最大重みクリーク抽出法における頂点集合の効率的な実装方法の提案

  清水悟司, 森中諒太, 山口一章, 増田澄男

  14 Sep. 2012, 平成24年度 情報処理学会関西支部 支部大会 講演論文集, 2012, Japanese

• グラフの階層直交描画における頂点座標決定アルゴリズム

  荒木徹也, 山口一章, 増田澄男

  22 Sep. 2011, 平成23年度 情報処理学会関西支部 支部大会 講演論文集, 2011, Japanese

• 最大重みクリーク抽出アルゴリズムの提案および実験的評価

  西尾達也, 山口一章, 増田澄男

  22 Sep. 2010, 平成22年度情報処理学会関西支部支部大会講演論文集, 2010, Japanese

• 頂点が大きさをもつグラフの描画アルゴリズム

  阿部昇, 増田澄男, 山口一章

  22 Sep. 2010, 平成22年度情報処理学会関西支部支部大会講演論文集, 2010, Japanese

• 組合せオークションの勝者決定問題における上界計算法の提案

  那須弘一郎, 田窪伸哉, 山口一章, 増田澄男

  22 Sep. 2010, 平成22年度情報処理学会関西支部支部大会講演論文集, 2010, Japanese

• 頂点とラベルの重なりを許した場合のグラフ描画における頂点ラベル配置法

  阿部昇, 増田澄男, 山口一章

  29 Sep. 2009, 平成21年度情報処理学会関西支部支部大会講演論文集, 2009, Japanese

• A proposal of point pattern retrieval algorithm

  MATSUDA Koji, NAKAMURA Masayuki, YAMAGUCHI Kazuaki, MASUDA Sumio

  10 Mar. 2009, 全国大会講演論文集, 71, 421 - 422, Japanese

• D-1-5 An Improvement on the Cycle Removal Step of a Drawing Algorithm for Directed Graphs

  Teramoto Masayuki, Masuda Sumio, Yamaguchi Kazuaki

  The Institute of Electronics, Information and Communication Engineers, 05 Mar. 2008, Proceedings of the IEICE General Conference, 2008 (1), 5 - 5, Japanese

• D-1-8 A Method for Creating Label Candidates to Place Labels of the Points and Chains on a Map

  Abe Noboru, Kusaki Masahiko, Masuda Sumio, Yamaguchi Kazuaki

  The Institute of Electronics, Information and Communication Engineers, 07 Mar. 2007, Proceedings of the IEICE General Conference, 2007 (1), 8 - 8, Japanese

• D-1-9 A FAST ALGORITHM FOR THE 2D POINT PATTERN MATCHING PROBLEM

  Shinohara Takahiro, Yamaguchi Kazuaki, Masuda Sumio

  The Institute of Electronics, Information and Communication Engineers, 07 Mar. 2007, Proceedings of the IEICE General Conference, 2007 (1), 9 - 9, Japanese

• D-1-10 AN IMPROVED ALGORITHM FOR MAP LABELING WITH LEADER LINES

  Isomura Yousuke, Masuda Sumio, Yamaguchi Kazuaki

  The Institute of Electronics, Information and Communication Engineers, 07 Mar. 2007, Proceedings of the IEICE General Conference, 2007 (1), 10 - 10, Japanese

• D-1-11 A PROPOSAL OF DATA STRUCTURE TO SPEED UP FOR FAST JUDGEMENT OF OVERLAPS OF GRAPHIC DATA

  Miki Youhei, Yamaguchi Kazuaki, Masuda Sumio

  The Institute of Electronics, Information and Communication Engineers, 07 Mar. 2007, Proceedings of the IEICE General Conference, 2007 (1), 11 - 11, Japanese

• An exact algorithm for the label placement problem

  INOUE Yuichi, YAMAGUCHI Kazuaki, MASUDA Sumio

  Given sites on a map and their labels with specified size, the label placement problem is to find an appropriate placement for each label. We consider the label placement problem in which the candidates for the position of each label are given. In this case the problem can be represented as the maximum independent set problem. In this paper, we propose a fast algorithm for finding a maximum independent set in a graph which is produced from the label placement problem. We show by some computer experiments that our algorithm is more efficient than the well-known algorithm.

  The Institute of Electronics, Information and Communication Engineers, 19 Apr. 2006, IEICE technical report, 106 (29), 63 - 67, Japanese

• D-1-3 Improvements of an Algorithm for the Map Labeling Problem with Priorities

  Abe Noboru, Hattori Shuji, Masuda Sumio, Yamaguchi Kazuaki

  The Institute of Electronics, Information and Communication Engineers, 08 Mar. 2006, Proceedings of the IEICE General Conference, 2006 (1), 3 - 3, Japanese

• An algorithm for generating vertex sequences to extract maximum weight cliques quickly

  YAMAGUCHI Kazuaki, MASUDA Sumio

  Given an undirected graph with weight for each vertex, the maximum weight clique problem is to find the clique of the maximum weight. When the maximum weight clique problem is solved with the branch-and-bound algorithm, it is important to calculate the tighter upper bounds of the weight of the maximum weight cliques quickly. Some exact algorithms to solve the maximum weight clique problem use the upper bound calculation with using longest paths on the graphs generated by some vertex sequences. In this paper, we propose a method to produce better vertex sequences. We show the efficiency of our algorithm with some experimental results.

  The Institute of Electronics, Information and Communication Engineers, 15 Sep. 2005, IEICE technical report. Theoretical foundations of Computing, 105 (273), 39 - 42, Japanese

• A fast algorithm for calculating an upper bound of the weight of the maximum weighted clique

  YAMAGUCHI Kazuaki, MASUDA Sumio

  We deal with the optimization problem that requies the maximum weighted clique of undirected graphs. Some exact algorithms based on the branch-and-bound method have been proposed. The computation time strongly depends on the tightness of upper bounds and the computation time of calculating upper bounds. In this paper we show a fast and simple algorithm for calculating upper bounds. We also show the effictiveness by some computational experiments.

  The Institute of Electronics, Information and Communication Engineers, 18 Apr. 2005, IEICE technical report. Theoretical foundations of Computing, 105 (7), 1 - 4, Japanese

• Algorithms for Map Labeling with Leader Lines

  OMORI Kazuki, MASUDA Sumio, YAMAGUCHI Kazuaki

  In this paper, we consider the problem of labeling points in the plane. For this problem, Wagner et al. proposed an efficient algorithm. It creates several label candidates (candidtaes of label positions) for each point and then determines label positions from the candidates. By extending this method, we present two algorithms for labeling points with leader lines. Our methods first apply the algorithm by Wagner et al. to the given set of points. Then the methods create label candidates with a leader line for each unlabeled point, and choose label positions from such cadidates.

  The Institute of Electronics, Information and Communication Engineers, 11 Mar. 2005, IEICE technical report. Theoretical foundations of Computing, 104 (743), 87 - 93, Japanese

• D-4-8 An Experimental Evaluation of Region Data Management System using Geographical Data

  Kumano Tatsuo, Yamaguchi Kazuaki, Masuda Sumio

  The Institute of Electronics, Information and Communication Engineers, 07 Mar. 2005, Proceedings of the IEICE General Conference, 2005 (1), 34 - 34, Japanese

• D-1-1 A Method for Creating Label Candidates for the Map Labeling Problem with Priorities

  Abe Noboru, Masuda Sumio, Yamaguchi Kazuaki

  The Institute of Electronics, Information and Communication Engineers, 07 Mar. 2005, Proceedings of the IEICE General Conference, 2005 (1), 1 - 1, Japanese

• D-4-9 An Improvement of TLAESA Nearest Neighbour Search Algorithm

  Tokoro Ken, Yamaguchi Kazuaki, Masuda Sumio

  The Institute of Electronics, Information and Communication Engineers, 07 Mar. 2005, Proceedings of the IEICE General Conference, 2005 (1), 35 - 35, Japanese

• D-1-2 A Method for Drawing a Rute Map Based on a Graph Drawing Algorithm

  Asada Nobuhiro, Masuda Sumio, Yamaguchi Kazuaki

  The Institute of Electronics, Information and Communication Engineers, 07 Mar. 2005, Proceedings of the IEICE General Conference, 2005 (1), 2 - 2, Japanese

• D-1-3 An Algorithm for Drawinga Hierarchical Graph with a Partition of the Vertex Setinto Groups

  Sakamoto Akira, Masuda Sumio, Yamaguchi Kazuaki

  The Institute of Electronics, Information and Communication Engineers, 07 Mar. 2005, Proceedings of the IEICE General Conference, 2005 (1), 3 - 3, Japanese

• An Exact Algorithm for Solving the Maximum Weighted Clique Problem with Using Comparability Supergraphs

  YAMAGUCHI Kazuaki, SAKAKIBARA Yoshie, MASUDA Sumio

  We show a method for calculating the upper bound of the weight of the maximum weighted clique problem with using comparability supergraphs. With our method, many algorithms for the maximum cadinality clique problem with using the branch-and-bound technique based on coloring are naturally extended to algorithms for the maximum weighted clique problem. Our method uses the maximum weighted clique in a comparability supergraph of the given graph at the bounding stage. We investigate the efficiency and the problems of our method some with some computational experiments.

  The Institute of Electronics, Information and Communication Engineers, 15 Apr. 2004, IEICE technical report. Theoretical foundations of Computing, 104 (16), 25 - 30, English

• A New Method to Obtain Relaxed Ploblems of the Maximum Clique Problem with using Chordal Supergraphs and Chordal Subgraphs

  NISHIDE Tomofumi, YAMAGUCHI Kazuaki, MASUDA Sumio

  It is known that Lagrangean relaxation is useful to obtain tight upper bounds for some combinatorial optimization problems. However, for the maximum clique problem, utilizing Lagrangean relaxation in a straight-forward manner does not give tight upper bounds. In this paper, we present two methods for obtaining good upper bounds for this problem. In order to construct relaxed problems, the first method makes several chordal supergraphs of the given graph, while the second one creates several vertex induced chordal subgraphs. Experimental results show that our methods can compute better upper bounds than the simple Lagrangean relaxation.

  The Institute of Electronics, Information and Communication Engineers, 11 Mar. 2003, IEICE technical report. Theoretical foundations of Computing, 102 (733), 15 - 22, Japanese

• A New Method to Obtain Upper Bound of the Stability Number of a Graph

  Yamaguchi Kazuaki, Nishide Tomofumi, Masuda Sumio

  The Institute of Electronics, Information and Communication Engineers, 07 Mar. 2002, Proceedings of the IEICE General Conference, 2002 (1), 3 - 3, Japanese

• An Algorithm for Drawing a Graph with Edge Labels

  Abe Noboru, Masuda Sumio, Yamaguti Kazuaki

  The Institute of Electronics, Information and Communication Engineers, 07 Mar. 2002, Proceedings of the IEICE General Conference, 2002 (1), 2 - 2, Japanese

• グラフ最適化問題に対する緩和問題の構成法の提案

  山口一章

  2002, FIT2002講演論文集

• An Algorithm for Labeling Edges in a Graph Drawing

  ABE Noboru, MASUDA Sumio, YAMAGUCHI Kazuaki

  Let G be a graph and Γ be its drawing on a plane. Each edge in G has a label of specified size. We consider the problem of placing many edge labels in Γ in such a way that no label overlaps vertices, edges or other labels. Recently, Kakoulis and Tollis proposed a heuristic algorithm for this problem. In this paper, we improve their algorithm by refining the part for deciding the candidates of label positions and that for choosing the final label positions.

  The Institute of Electronics, Information and Communication Engineers, 09 Apr. 2001, IEICE technical report. Theoretical foundations of Computing, 101 (5), 9 - 16, Japanese

• An algorithm for finding shortest paths in undirected graphs with using the nearest neighbor search technique

  YAMAGUCHI Kazuaki, IWAMI Yohei, MASUDA Sumio

  We deal with the problem to find a shortest path between two specified vertices. This problem can be efficiently solved with A^* algorithm, used in AI field, if we roughly know the distance from each vertex to the goal vertex. On the other hand, LAESA, one of nearest neighbor search algorithms, uses "approximate distance" to solve NNS problem efficiently. In this paper, we show that approximate disntace can be applied to A^* algorithm, and that we can efficiently obtain shortest paths with this method.

  The Institute of Electronics, Information and Communication Engineers, 09 Apr. 2001, IEICE technical report. Theoretical foundations of Computing, 101 (5), 17 - 22, Japanese

• An Improvement on a Multi-layer Data Structure Based on a BD tree

  NAKANO Satoru, MASUDA Sumio, YAMAGUCHI Kazuaki

  The range search performance of a BD(M) tree, which is a multi-layer data structure based on a BD tree, highly depends on the value of parameter n. In this paper, we present a multi-layer data structure, called an S2M structure. It includes two BD(M) trees with distinct values of n, and selects an appropreate one depending on the search condition. Experimental results show that S2M strucutures are superior to other multi-layer data structures, such as ST structures, MT structures and BD(M) trees, with respect to range search performance.

  The Institute of Electronics, Information and Communication Engineers, 09 Mar. 2001, IEICE technical report. Theoretical foundations of Computing, 100 (705), 97 - 104, Japanese

• An Algorithm for NNS using distance approximation from multi reference points

  Moritsu Masaomi, Yamaguchi Kazuaki, Tanaka Eiichi

  The Institute of Electronics, Information and Communication Engineers, 07 Mar. 2001, Proceedings of the IEICE General Conference, 2001 (1), 51 - 51, Japanese

• A fast algorithm for nearest neighbor search in general metric spaces

  YAMAGUCHI Kazuaki, KONDO Yoichi, TANAKA Eiichi

  Given a point set S, the nearest neighor search problem is to construct a data structure so that the nearest point to a query point can be found quickly. LAESA is considered to be one of the most efficient data structure with size O(|S|), but its running time is linear to |S|. In this paper, we propose a new data structure with size O(|S|), cvp-structure. It requires about same number of distance computations as LAESA, and the time complexity is linear to the number of distance computations. Thus, our data structure is more effcient than LAESA.

  The Institute of Electronics, Information and Communication Engineers, 06 Oct. 2000, IEICE technical report. Data engineering, 100 (351), 65 - 70, Japanese

• An improvement of LAESA to find nearest neighbors

  KONDO Yoichi, YAMAGUCHI Kazuaki, TANAKA Eiichi

  Nearest neighbor search is to find the nearest site to query point from a set S of n sites, and it is one of the important parts of pattern recognition. We introduce an improvement of LAESA to find nearest neighbors in general metric spaces. Our algorithm is especially efficient when distance computations are very expensive, and when the size of data structure is limited. The results of experiments show that in this case our algorithm finds nearest neighbors faster than LAESA, which can be considered as one of the most efficent algorithms so far.

  The Institute of Electronics, Information and Communication Engineers, 11 Sep. 2000, IEICE technical report. Theoretical foundations of Computing, 100 (289), 9 - 15, Japanese

• An Algorithm for Placing Vertex Labels in a Graph Drawing

  KIKUCHI Gento, MASUDA Sumio, YAMAGUCHI Kazuaki

  In this paper, we consider the problem of placing vertex labels in a drawing of an undirected graph. Kamada has presented a very simple method for this problem. However, if the labels are not small, it often yields the overlaps between labels and other objects. This paper shows a method for placing many labels with no such overlaps. This method first determines, for each vertex v, the set of candidates of its label positions. At this step, the existence of edges around v and the label size of v are considered. Then, the method places labels one by one. If the label of a vertex v overlaps other vertices or labels, the label positions are locally adjusted or another candidate of label position for v is selected.

  The Institute of Electronics, Information and Communication Engineers, 11 Sep. 2000, IEICE technical report. Theoretical foundations of Computing, 100 (289), 41 - 46, Japanese

• A Fair Assignment Algorithm for Class Assignment Problems

  KITA Takayuki, SHIBAYAMA Tosimitu, YAMAGUCHI Kazuaki, MASUDA Sumio

  The class assignment problem is to assign students to classes within the capacity of each class, in such a way that it satisfies them as much as possible. We can consider the problem as a kind of resource allocation problems. It is generally impossible to assign the students so that all of them are satisfied. We propose an assignment algorithm which reduces students assigned to the classes they do not want. The results of experiments show that our algorithm produces less number of those students than other known algorithms, and also show that knowing other students' choices is not profitable for any students.

  The Institute of Electronics, Information and Communication Engineers, 11 Sep. 2000, IEICE technical report. Theoretical foundations of Computing, 100 (289), 17 - 23, Japanese

• Experimental Performance of an Approximation Algorithm for the Capacitated k - Center Problem

  KOTANI Tomoaki, YAMAGUCHI Kazuaki, MASUDA Sumio

  The k-center problem is one of the important NP optimization problems. The capacitated k-center problem is its more practical variation. Although a 6-approximation algorithm has been proposed, it is considered to be ineffective. In this paper, we present three heuristic algorithms for the capacitated k-center problem. Experimental results show that we can get better solutions more efficiently, by executing two of our methods sequentially.

  Information Processing Society of Japan (IPSJ), 17 Jan. 2000, IPSJ SIG Notes, 2000 (5), 49 - 56, Japanese

• Improved Methods for Splitting Line Segments in a GBD Tree

  INO Atsushi, MASUDA Sumio, YAMAGUCHI Kazuaki

  A GBD tree is a data structure that can maintain a set of line segments on a plane. By using it, we can efficiently perform three kinds of operations; insertion, deletion and range search. However, the search performance is not good enough if long line segments exist. In order to improve it, a method for splitting long line segments was proposed. In this article, we show that some modifications of the splitting method further improve the search performance.

  Information Processing Society of Japan (IPSJ), 17 Jan. 2000, IPSJ SIG Notes, 2000 (5), 81 - 87, Japanese

• Data structure and algorithm for nearest neighbour search

  Yamaguchi Kazuaki, Tanaka Eiichi, Shirasaka Yoshinari

  Many algorithms for finding nearest neighbours have been introduced recently. We introduce a new data structure and algorithm to find nearest neighbours in general metric spaces, where distance computations are very expensive. The results of experiments show that in some cases our algorithms find nearest neighbours with less distance computations than LAESA, which can be considered as one of the most efficient algorithms so far.

  The Institute of Electronics, Information and Communication Engineers, 23 Jan. 1999, IEICE technical report. Theoretical foundations of Computing, 98 (562), 73 - 80, Japanese

• Routing methods on a packet network based on game theory

  Honda Shinichiro, Yamaguchi Kazuaki, Masuda Sumio

  The Institute of Electronics, Information and Communication Engineers, 06 Mar. 1998, Proceedings of the IEICE General Conference, 1998 (2), 230 - 230, Japanese

• A study on routing methods in line switching networks

  Kamata Masahiko, Yamaguchi Kazuaki

  The Institute of Electronics, Information and Communication Engineers, 06 Mar. 1998, Proceedings of the IEICE General Conference, 1998 (2), 229 - 229, Japanese

• A study on routing methods of packet networks

  Iwazawa Yoriaki, Yamaguti Kazuaki, Masuda Sumio

  The Institute of Electronics, Information and Communication Engineers, 06 Mar. 1998, Proceedings of the IEICE General Conference, 1998 (2), 226 - 226, Japanese

• Simultaneous planar drawing of some graphs

  YAMAGUCHI Kazuaki, AKASHI Yoshiki, KASHIWABARA Toshinobu

  If each drawing of G_1=(V, E_1), G_2=(V, E_2),…, G_k=(V, E_k) is planar in a drawing of a graph G=(V, E_1 ∪ E_2 ∪…∪ E_k), the drawing of G is called a simultaneous planar drawing of G_1, G_2,…, and G_k. K-graphs sinultaneous planar problem is to examine if there exists any simultaneous planar drawing of G_1,…G_k or not. This paper proves that 3-graphs simultaneous planar problem is NP-complete.

  The Institute of Electronics, Information and Communication Engineers, 26 Sep. 1997, IEICE technical report. Theoretical foundations of Computing, 97 (290), 1 - 4, Japanese

• The complexity of the Shortest Path Problem under obstructions : the case visited arcs cannot be obstructed

  YAMAGUCHI Kazuaki, ARAKI Toshiro, KASHIWABARA Toshinobu

  Let G = (V,A) be a directed graph with (positive) length l(a) for each a ∈ A, and two vertices s and t are specified. Two players, P1 and P2, play reciprocally on G according to the following rules until Pl reaches t. P1 attempts to move from starting points to destination t, moving along one arc during each turn. P2 deletes arcs, whose start points weren't visited by P1, from A during his turn. The number of arcs which P2 can delete within a game is K. Pl tries to keep the sum of the length of arcs which he passed through to a minimum value, while P2 attempts to make it as large as possible. What value will it be? In this paper, we show that, the problem can be solved in O(m + nlogn) time (m=|A|,n=|V|) in the case K=1, and that it is NP-hard in the case K≥2, even if l(a) = 1 for all a ∈ A.

  The Institute of Electronics, Information and Communication Engineers, 16 Nov. 1995, IEICE technical report. Circuits and systems, 95 (351), 71 - 76, Japanese

• Shortest path under obstruction

  Yamaguchi Kazuaki, Araki Toshiro, Kashiwabara Toshinobu

  グラフが変化する事を考慮にいれた最短経路問題の一つとして本稿では次のような問題を考える.

  The Institute of Electronics, Information and Communication Engineers, 27 Mar. 1995, Proceedings of the IEICE General Conference, 1995, 3 - 3, Japanese

• NP - completeness of computing a common st - numbering for two planar graph

  YAMAGUCHI Kazuaki, HARADA Toshihiko

  Given a 2-connected graph G(V, E) and its one edge st(s, t ε V), an st-numbering is the numbering such that s is given the number 1, t is given the number |V|, and for all other vertices there are lower numbered adjacent vertices and higher numbered adjacent vertices. A Planar graph is a graph which can be drawn on a plane in such a way that no two edges cross each other. In this paper, for two planar graphs that have a common vertex set, we consider the problem of giving a numbering for those vertices that is an st-numbering for each graph. We show it is NP-complete.

  Information Processing Society of Japan (IPSJ), 17 Mar. 1995, IPSJ SIG Notes, 1995 (32), 53 - 60, Japanese

• NP-Completeness of interval graph completion from a path graph

  Yamaguchi Kazuaki, Araki Toshiro, Kashiwabara Toshinobu

  An undirected graph is called a path graph,if its vertices correspond to paths on a fixed tree and two vertices are connected by an edge if and only if their corresponding paths have non empty intersection.Let A be a set of intervals on a linearly ordered set. An undirected graph is called an interval graph,if its vertices correspond to intervals of A and two vertices are connected by an edge if and only if their corresponding intervals have non empty intersection.This paper proves that the problem of deciding whether we can transform a path graph to an interval graph by adding less than K edges is NP complete.

  The Institute of Electronics, Information and Communication Engineers, 27 May 1993, IEICE technical report. Theoretical foundations of Computing, 93 (81), 15 - 20, Japanese

Presentations

• 貪欲法に基づいた巡回セールスマンアルゴリズムの評価と改良

  杉本 拓哉, 阿部 昇, 山口 一章

  令和５年電気学会全国大会, 16 Mar. 2023, Japanese

• ビームサーチを用いたグラフ彩色アルゴリズム

  明石健太郎, 山口一章

  平成4年電気関係学会関西連合大会, 26 Nov. 2022, Japanese

  Oral presentation

• 最大重みクリーク問題に関する厳密解法

  山口 一章

  平成4年電気関係学会関西連合大会, 26 Nov. 2022, Japanese

  [Invited]

  Invited oral presentation

• 描画領域の大きさを考慮したデフォルメ路線図に対する駅名配置アルゴリズム

  木田光太朗, 増田澄男, 山口一章

  令和元年電気関係学会関西連合大会, 01 Dec. 2019, Japanese

  Oral presentation

• 描画領域が制限されたデフォルメ路線図の作成

  高尾祐矢, 増田澄男, 山口一章

  令和元年電気関係学会関西連合大会, 01 Dec. 2019, Japanese

  Oral presentation

• 部分再構築法を用いた彩色問題の近似アルゴリズム

  梅本奏真, 山口一章, 増田澄男

  令和元年電気関係学会関西連合大会, 01 Dec. 2019, Japanese

  Oral presentation

• 部分再構築法に基づくグラフ埋め込みアルゴリズム

  谷口晴亮, 山口一章, 増田澄男

  令和元年電気関係学会関西連合大会, 01 Dec. 2019, Japanese

  Oral presentation

• ハイパーリーダを用いた多対一外周ラベル配置アルゴリズム

  濱岡航平, 増田澄男, 山口一章

  令和元年電気関係学会関西連合大会, 01 Dec. 2019, Japanese

  Oral presentation

• 負の重みを許した最大辺重みクリーク問題に関する研究

  東俊介, 山口一章, 増田澄男

  令和元年電気関係学会関西連合大会, 01 Dec. 2019, Japanese

  Oral presentation

• Improved Heuristic for Linear Arrangement Problem

  TANAKA RYO, YAMAGUCHI KAZUAKI, MASUDA SUMIO

  情報処理学会関西支部大会, Sep. 2019, Japanese, 大阪大学中之島センター, Domestic conference

  Oral presentation

• グラフ彩色問題に対する局所探索法の実験的評価

  OOI TOMOHIRO, YAMAGUCHI KAZUAKI, MASUDA SUMIO

  2019 年度情報処理学会関西支部 支部大会, Sep. 2019, Japanese, 大阪大学中之島センター, Domestic conference

  Oral presentation

• 辺交差数と近接数を考慮した力指向グラフ描画アルゴリズム

  土井 裕実加, MASUDA SUMIO, YAMAGUCHI KAZUAKI

  平成30年電気関係学会関西連合大会, Dec. 2018, Japanese, Domestic conference

  Oral presentation

• 線形順序付け問題に対する焼きなまし法の近傍選択法

  兼本 樹, YAMAGUCHI KAZUAKI, MASUDA SUMIO

  平成30年電気関係学会関西連合大会, Dec. 2018, Japanese, Domestic conference

  Oral presentation

• ラベルの縦書きを許した場合のラベル配置アルゴリズム

  田澤 直也, MASUDA SUMIO, YAMAGUCHI KAZUAKI

  平成30年電気関係学会関西連合大会, Dec. 2018, Japanese, Domestic conference

  Oral presentation

• Limited Discrepancy Searchによるグラフ彩色

  周 子言, YAMAGUCHI KAZUAKI, MASUDA SUMIO

  平成30年電気関係学会関西連合大会, Dec. 2018, Japanese, Domestic conference

  Oral presentation

• An exact algorithm for the map labeling problem

  KIDO NAOTO, MASUDA SUMIO, YAMAGUCHI KAZUAKI

  2018 年度情報処理学会関西支部 支部大会, Sep. 2018, Japanese, 大阪大学中之島センター（台風のため中止）, Domestic conference

  Poster presentation

• A study on a branch-bound algorithm for the maximum edge-weight clique problem

  IKEDA SOUSHI, YAMAGUCHI KAZUAKI, MASUDA SUMIO

  2018 年度情報処理学会関西支部 支部大会, Sep. 2018, Japanese, 大阪大学中之島センター（台風のため中止）, Domestic conference

  Oral presentation

• An improved algorithm for drawing a hierarchical graph with vertices spanning two layers

  IKEDA KOICHIRO, MASUDA SUMIO, YAMAGUCHI KAZUAKI

  2018 年度情報処理学会関西支部 支部大会, Sep. 2018, Japanese, 大阪大学中之島センター（台風のため中止）, Domestic conference

  Poster presentation

• 有向グラフ描画における矢じり配置問題に対する厳密解法

  KIDO NAOTO, MASUDA SUMIO, YAMAGUCHI KAZUAKI

  情報処理学会アルゴリズム研究会 第167回研究会, Mar. 2018, Japanese, Domestic conference

  Oral presentation

• Limited Discrepancy Search によるフィードバック辺集合の探索

  KANEMOTO ITSUKI, YAMAGUCHI KAZUAKI, MASUDA SUMIO

  情報処理学会アルゴリズム研究会 第167回研究会, Mar. 2018, Japanese, 高松, Domestic conference

  Oral presentation

• 辺重み付きグラフからのクリーク群抽出による構造分析

  ISHIHARA RYOTA, YAMAGUCHI KAZUAKI, MASUDA SUMIO

  第116回数理モデル化と問題解決研究発表会, Dec. 2017, Japanese, 奈良女子大学, Domestic conference

  Oral presentation

• 辺交差数を考慮した力指向グラフ描画アルゴリズムの改良

  DOI YUMIKA, MASUDA SUMIO, YAMAGUCHI KAZUAKI

  平成29年電気関係学会関西連合大会, Nov. 2017, Japanese, 近畿大学東大阪キャンパス, Domestic conference

  Oral presentation

• 辺に重みのあるグラフからのクリーク群抽出問題に関する研究

  OUNISHI KAITO, ISHIHARA RYOTA, YAMAGUCHI KAZUAKI, MASUDA SUMIO

  平成29年電気関係学会関西連合大会, Nov. 2017, Japanese, 近畿大学東大阪キャンパス, Domestic conference

  Oral presentation

• 折れ線配置アルゴリズムの拡張とデフォルメ路線図作成への応用

  ICHINOSE TAKUMI, MASUDA SUMIO, YAMAGUCHI KAZUAKI

  平成29年電気関係学会関西連合大会, Nov. 2017, Japanese, 近畿大学東大阪キャンパス, Domestic conference

  Oral presentation

• 最大重みクリークの厳密解法の挙動に関する一考察

  KADOE DAIKI, YAMAGUCHI KAZUAKI, MASUDA SUMIO

  平成29年電気関係学会関西連合大会, Nov. 2017, Japanese, 近畿大学東大阪キャンパス, Domestic conference

  Oral presentation

• スライダーモデルを用いた有向グラフ描画における矢じり配置手法

  KIDO NAOTO, MASUDA SUMIO, YAMAGUCHI KAZUAKI

  平成29年電気関係学会関西連合大会, Nov. 2017, Japanese, 近畿大学東大阪キャンパス, Domestic conference

  Oral presentation

• 2階層にまたがる頂点をもつグラフの描画アルゴリズム

  IKEDA KOUICHIROU, MASUDA SUMIO, YAMAGUCHI KAZUAKI

  平成29年電気関係学会関西連合大会, Nov. 2017, Japanese, 近畿大学東大阪キャンパス, Domestic conference

  Oral presentation

• 分枝限定法による最大辺重みクリーク抽出法

  清水 悟司, YAMAGUCHI KAZUAKI, MASUDA SUMIO

  情報処理学会アルゴリズム研究会, Nov. 2016, Japanese, Domestic conference

  Oral presentation

• 最大重みクリーク抽出におけるLimited Discrepancy Searchの効果に関する実験的評価

  島村 祥平, YAMAGUCHI KAZUAKI, SAITOH TOSHIKI, MASUDA SUMIO

  平成28年電気関係学会関西連合大会, Nov. 2016, Japanese, Domestic conference

  Oral presentation

• 階層数に制限がある場合の有向グラフの階層化

  宮崎 拓也, MASUDA SUMIO, SAITOH TOSHIKI, YAMAGUCHI KAZUAKI

  平成28年電気関係学会関西連合大会, Nov. 2016, Japanese, Domestic conference

  Oral presentation

• 階層グラフ描画における辺交差数削減のための道の移動処理について

  西岡 祥, MASUDA SUMIO, SAITOH TOSHIKI, YAMAGUCHI KAZUAKI

  平成28年電気関係学会関西連合大会, Nov. 2016, Japanese, Domestic conference

  Oral presentation

• スライダーモデルを用いたグラフ描画における辺のラベル配置アルゴリズム

  山地 拓郎, MASUDA SUMIO, SAITOH TOSHIKI, YAMAGUCHI KAZUAKI

  平成28年電気関係学会関西連合大会, Nov. 2016, Japanese, Domestic conference

  Oral presentation

• 辺の重みを考慮したクリーク分割に対する発見的手法

  半田 晃大朗, YAMAGUCHI KAZUAKI, SAITOH TOSHIKI, MASUDA SUMIO

  日本オペレーションズ・リサーチ学会関西支部若手研究会, Oct. 2016, Japanese, Domestic conference

  Poster presentation

• 折れ線の配置によるデフォルメ路線図作成について

  多鹿 雄策, 一ノ瀬 拓海, MASUDA SUMIO, SAITOH TOSHIKI, YAMAGUCHI KAZUAKI

  日本オペレーションズ・リサーチ学会関西支部若手研究会, Oct. 2016, Japanese, Domestic conference

  Poster presentation

• 整数計画法を用いたデフォルメ路線図改良法

  一ノ瀬 拓海, 多鹿 雄策, MASUDA SUMIO, SAITOH TOSHIKI, YAMAGUCHI KAZUAKI

  2016年度情報処理学会関西支部支部大会, Sep. 2016, Japanese, Domestic conference

  Oral presentation

• 最大辺重みクリーク問題に対する局所探索法の実験的評価

  清水 悟司, 石原 諒太, YAMAGUCHI KAZUAKI, MASUDA SUMIO

  2016年度情報処理学会関西支部支部大会, Sep. 2016, Japanese, Domestic conference

  Oral presentation

• 最大重み独立頂点集合問題に対する高速な発見的手法の提案

  清水 悟司, YAMAGUCHI KAZUAKI, SAITOH TOSHIKI, MASUDA SUMIO

  電子情報通信学会コンピュテーション研究会, Apr. 2016, Japanese, Domestic conference

  Oral presentation

• 階層グラフ描画の辺交差数削減のための道の移動処理の改良

  OKUMURA SHOHEI, MASUDA SUMIO, SAITOH TOSHIKI, YAMAGUCHI KAZUAKI

  平成27年電気関係学会関西連合大会, Nov. 2015, Japanese, 寝屋川市，摂南大学, Domestic conference

  Oral presentation

• 双方向グラフの最大重み最小帰還辺集合問題について

  ARAKI TETSUYA, MASUDA SUMIO, SAITOH TOSHIKI, YAMAGUCHI KAZUAKI

  日本応用数理学会2015年年会, Sep. 2015, Japanese, 金沢大学角真キャンパス, 任意の有向グラフを G = (V,E) とする．任意の 2 頂点 v,w ∈ V に対し， (v → w) ∈ E であるとき且つそのときに限り (w → v) ∈ E であるならば， G を双方向グラフと呼ぶ．本研究 では，各辺が非負の重みをもつ 双方向グラフG が与えられたときに，その最小帰還辺集合のうち，辺の重みの総和が最大のものを求める問題を考える．この問題は，階層グラフに対して， 辺の交差が少ない直交描画を求める問題に応用可能である．, Domestic conference

  Oral presentation

• 最大重みクリーク問題に対する分枝限定法に基づく近似 解法に関する研究

  SHIBANO SATORU, YAMAGUCHI KAZUAKI, SAITOH TOSHIKI, MASUDA SUMIO

  2015年度情報処理学会関西支部支部大会, Sep. 2015, Japanese, 大阪大学中之島キャンパス, Domestic conference

  Oral presentation

• 階層グラフ描画におけるダミー頂点数削減を目的とした階層再割当てアルゴリズム

  野口 翔大, MASUDA SUMIO, YAMAGUCHI KAZUAKI

  2015年電子情報通信学会総合大会（学生ポスターセッション）, Mar. 2015, Japanese, Domestic conference

  Poster presentation

• 辺の折れ曲がりを許したグラフレイアウト調整アルゴリズム

  塚本 和樹, MASUDA SUMIO, SAITOH TOSHIKI, YAMAGUCHI KAZUAKI, 阿部 昇

  平成26年電気関係学会関西連合大会, Nov. 2014, Japanese, Domestic conference

  Poster presentation

• 階層グラフの直交描画における辺交差数削減

  荒木 徹也, MASUDA SUMIO, YAMAGUCHI KAZUAKI

  平成26年電気関係学会関西連合大会, Nov. 2014, Japanese, Domestic conference

  Poster presentation

• ある最大重みクリーク抽出法の前処理に関する一考察

  近藤 広樹, YAMAGUCHI KAZUAKI, SAITOH TOSHIKI, MASUDA SUMIO

  平成26年電気関係学会関西連合大会, Nov. 2014, Japanese, Domestic conference

  Poster presentation

• 4 スライダーモデルとルール処理を用いたラベル配置アルゴリズム

  寺脇 宏高, MASUDA SUMIO, SAITOH TOSHIKI, YAMAGUCHI KAZUAKI

  平成26年電気関係学会関西連合大会, Nov. 2014, Japanese, Domestic conference

  Poster presentation

• 分枝限定法における新たな探索法の提案

  YAMAGUCHI KAZUAKI, SAITOH TOSHIKI, MASUDA SUMIO

  人工知能学会人工知能基本問題研究会, Oct. 2014, Japanese, Domestic conference

  Oral presentation

• 最小重み頂点被覆問題に対する線形時間の発見的手法の提案

  田中 智之, YAMAGUCHI KAZUAKI, SAITOH TOSHIKI, MASUDA SUMIO

  2014年度情報処理学会関西支部支部大会, Sep. 2014, Japanese, Domestic conference

  Oral presentation

• Exact Algorithms for B-Bandwidth Problem with Restricted B

  SAITOH TOSHIKI, Yukumoto Hiroshi, YAMAGUCHI KAZUAKI, MASUDA SUMIO

  KOREA-JAPAN Joint Workshop on Algorithms and Computation (WAAC 2012), Jul. 2014, English, International conference

  Oral presentation

• 2種類の優先度を考慮したラベル配置アルゴリズム

  ABE Noboru, AMAI Yoshinori, NAKATAKE Toshinori, MASUDA SUMIO, YAMAGUCHI KAZUAKI

  日本オペレーションズ・リサーチ学会2014年春季研究発表会, Mar. 2014, Japanese, 大阪大学, Domestic conference

  Oral presentation

• あみだくじを数え上げる省領域アルゴリズムについて

  中嶋 章裕, SAITOH TOSHIKI, 山口 一章, 増田 澄男

  組合せゲーム・パズルミニ研究集会, Feb. 2014, Japanese, Domestic conference

  Oral presentation

• 施設配置問題に対する遺伝的アルゴリズムの高速化

  OKADA Satoshi, YAMAGUCHI KAZUAKI, SAITOH TOSHIKI, MASUDA SUMIO

  平成25年電気関係学会関西連合大会, Nov. 2013, Japanese, 寝屋川市, Domestic conference

  Poster presentation

• 最大クリーク問題に対する発見的手法の高速化に関する研究

  MORINAKA Ryota, YAMAGUCHI KAZUAKI, SAITOH TOSHIKI, MASUDA SUMIO

  平成25年電気関係学会関西連合大会, Nov. 2013, Japanese, 寝屋川市, Domestic conference

  Poster presentation

• 階層グラフ描画における辺交差数を考慮したダミー頂点共有化処理

  HORIO Akihisa, ARAKI Tetsuya, MASUDA SUMIO, SAITOH TOSHIKI, YAMAGUCHI KAZUAKI

  平成25年電気関係学会関西連合大会, Nov. 2013, Japanese, 寝屋川市, Domestic conference

  Poster presentation

• 階層グラフ描画における頂点順序決定アルゴリズムの提案

  MATOBA Ikunori, ARAKI Tetsuya, MASUDA SUMIO, SAITOH TOSHIKI, YAMAGUCHI KAZUAKI

  平成25年電気関係学会関西連合大会, Nov. 2013, Japanese, 寝屋川市, Domestic conference

  Poster presentation

• 動的計画法を用いた有向二値完全系統樹の効率のよい列挙

  森戸 一貴, SAITOH TOSHIKI, 山口 一章, 増田 澄男

  コンピュテーション研究会, May 2013, Japanese, Domestic conference

  Oral presentation

• 階層グラフの直交描画アルゴリズム

  ARAKI Tetsuya, MASUDA SUMIO, MATOBA Ikunori, YAMAGUCHI KAZUAKI, SAITOH TOSHIKI

  電子情報通信学会コンピュテーション研究会, Apr. 2013, Japanese, 神戸市, Domestic conference

  Oral presentation

• 動的計画法を用いた上界計算法による最大重みクリーク抽出アルゴリズムの提案

  SHIMIZU SATOSHI, YAMAGUCHI KAZUAKI, SAITOH TOSHIKI, MASUDA SUMIO

  電子情報通信学会コンピュテーション研究会, Mar. 2013, Japanese, Domestic conference

  Oral presentation

• 部分再構築操作を組み込んだGAによるFacility Dispersion問題の解法

  YAMADA MITSUHIRO, YAMAGUCHI KAZUAKI, SAITOH TOSHIKI, MASUDA SUMIO

  進化計算シンポジウム2012, Dec. 2012, Japanese, Domestic conference

  Poster presentation

• 二つのクラスに割り当てる割当問題に対する割当法の提案

  松永 涼, YAMAGUCHI KAZUAKI, MASUDA SUMIO

  平成24年電気関係学会関西連合大会, Dec. 2012, Japanese, 吹田市, Domestic conference

  Poster presentation

• 組合せオークションの勝者決定問題に対する複数の上界計算を用いた厳密解法

  白川 達也, 黒田 陽一朗, YAMAGUCHI KAZUAKI, MASUDA SUMIO

  平成24年電気関係学会関西連合大会, Dec. 2012, Japanese, 吹田市, Domestic conference

  Poster presentation

• 最大クリークを求める進化型アルゴリズムに関する一考察

  山崎 渉, YAMAGUCHI KAZUAKI, MASUDA SUMIO

  平成24年電気関係学会関西連合大会, Dec. 2012, Japanese, 吹田市, Domestic conference

  Poster presentation

• 固定位置モデルを用いたラベル配置アルゴリズムの改良

  奥村 潤, MASUDA SUMIO, YAMAGUCHI KAZUAKI

  平成24年電気関係学会関西連合大会, Dec. 2012, Japanese, 吹田市, Domestic conference

  Poster presentation

• 階層グラフ描画の頂点座標決定法に関する一考察

  的場 郁典, MASUDA SUMIO, YAMAGUCHI KAZUAKI

  平成24年電気関係学会関西連合大会, Dec. 2012, Japanese, 吹田市, Domestic conference

  Poster presentation

• 階層グラフ描画におけるダミー頂点共有化処理の改良

  堀尾 明久, 荒木 徹也, MASUDA SUMIO, YAMAGUCHI KAZUAKI

  平成24年電気関係学会関西連合大会, Dec. 2012, Japanese, 吹田市, Domestic conference

  Poster presentation

• Edge concentrationを 用いた交差数最小化問題に対するGAの適用

  OKADA SATOSHI, YAMAGUCHI KAZUAKI, SAITOH TOSHIKI, MASUDA SUMIO

  進化計算シンポジウム2012, Dec. 2012, Japanese, Domestic conference

  Poster presentation

• 最大重みクリーク抽出法における分枝順序の検討

  森中 諒太, 清水 悟司, YAMAGUCHI KAZUAKI, MASUDA SUMIO

  平成24年度情報処理学会関西支部支部大会, Sep. 2012, Japanese, 大阪市, Domestic conference

  Oral presentation

• 階層グラフの直交描画における線分座標決定

  ARAKI TETSUYA, YAMAGUCHI KAZUAKI, MASUDA SUMIO

  平成24年度情報処理学会関西支部支部大会, Sep. 2012, Japanese, 大阪市, Domestic conference

  Oral presentation

• ある最大重みクリーク抽出法における頂点集合の効率的な実装方法の提案

  清水 悟司, 森中 諒太, YAMAGUCHI KAZUAKI, MASUDA SUMIO

  平成24年度情報処理学会関西支部支部大会, Sep. 2012, Japanese, 大阪市, Domestic conference

  Poster presentation

• グラフの直交描画アルゴリズムを用いたデフォルメ路線図作成法の改良

  三好 貴洋, 増田 澄男, 山口 一章

  2012年電子情報通信学会総合大会（学生ポスターセッション）, Mar. 2012, Japanese, 岡山大学, Domestic conference

  Poster presentation

• 複数の上界計算法による最大重みクリーク抽出法

  黒田 陽一朗, 山口 一章, 増田 澄男

  平成23年電気関係学会関西連合大会, Oct. 2011, Japanese, 兵庫県立大学姫路書写キャンパス, Domestic conference

  Poster presentation

• 頂点の位置関係が指定されたグラフの描画アルゴリズム

  林 均, 増田 澄男, 山口 一章

  平成23年電気関係学会関西連合大会, Oct. 2011, Japanese, 兵庫県立大学姫路書写キャンパス, Domestic conference

  Poster presentation

• 頂点が幅をもつ階層グラフ描画の頂点配置改善法

  竹内 大和, 増田 澄男, 山口 一章

  平成23年電気関係学会関西連合大会, Oct. 2011, Japanese, 兵庫県立大学姫路書写キャンパス, Domestic conference

  Poster presentation

• スライダーモデルとルール処理を用いた優先度付きラベル配置アルゴリズム

  鷲田 拓也, 増田 澄男, 山口 一章

  平成23年電気関係学会関西連合大会, Oct. 2011, Japanese, 兵庫県立大学姫路書写キャンパス, Domestic conference

  Poster presentation

• あるクラス割当問題に関する一考察

  有山 貴士, 山口 一章, 増田 澄男

  平成23年電気関係学会関西連合大会, Oct. 2011, Japanese, 兵庫県立大学姫路書写キャンパス, Domestic conference

  Poster presentation

• グラフの階層直交描画における頂点座標決定アルゴリズム

  荒木 徹也, 増田 澄男, 山口 一章

  平成23年度情報処理学会関西支部支部大会, Sep. 2011, Japanese, 情報処理学会関西支部, 大阪大学中之島センター, Domestic conference

  Oral presentation

• 非連結無向グラフに対する力指向描画アルゴリズムの改良

  KODAMA Norihiko, MASUDA Sumio, YAMAGUCHI Kazuaki

  平成22年電気関係学会関西連合大会, Nov. 2010, Japanese, 草津市, Domestic conference

  Poster presentation

• 頂点が幅をもつ階層グラフ描画の頂点座標決定法

  MURATA Syouta, ARAKI Tetsuya, MASUDA Sumio, YAMAGUCHI Kazuaki

  平成22年電気関係学会関西連合大会, Nov. 2010, Japanese, 草津市, Domestic conference

  Poster presentation

• 組合せオークションの勝者決定問題に対する一考察

  TAKUBO Shinya, YAMAGUCHI Kazuaki, MASUDA Sumio

  平成22年電気関係学会関西連合大会, Nov. 2010, Japanese, 草津市, Domestic conference

  Poster presentation

• 頂点が大きさをもつグラフの描画アルゴリズム

  ABE Noboru, MASUDA Sumio, YAMAGUCHI Kazuaki

  平成22年度情報処理学会関西支部支部大会, Sep. 2010, Japanese, 情報処理学会関西支部, 大阪市, Domestic conference

  Oral presentation

• 組合せオークションの勝者決定問題における上界計算法の提案

  NASU Kouichirou, YAMAGUCHI Kazuaki, MASUDA Sumio

  平成22年度情報処理学会関西支部支部大会, Sep. 2010, Japanese, 情報処理学会関西支部, 大阪市, Domestic conference

  Oral presentation

• 最大重みクリーク抽出アルゴリズムの提案および実験的評価

  NISHIO Tatsuya, YAMAGUCHI Kazuaki, MASUDA Sumio

  平成22年度情報処理学会関西支部支部大会, Sep. 2010, Japanese, 情報処理学会関西支部, 大阪市, Domestic conference

  Oral presentation

• 階層グラフ描画における頂点座標決定アルゴリズム

  ARAKI Tetsuya, YAMAGUCHI Kazuaki, MASUDA Sumio, MURATA Syouta

  平成22年度情報処理学会関西支部支部大会, Sep. 2010, Japanese, 情報処理学会関西支部, 大阪市, Domestic conference

  Oral presentation

• 優先度付きラベルサイズ最大化アルゴリズムの提案

  Yusuke Mizuno, Sumio Masuda, kazuaki Yamaguchi

  平成21年電気関係学会関西支部連合大会, Nov. 2009, Japanese, 電気関係学会関西支部, 吹田市, Domestic conference

  Poster presentation

• 非連結無向グラフに対する力指向描画アルゴリズム

  Norihiko Kodama, Sumio Masuda, Kazuaki Yamaguchi

  平成21年電気関係学会関西支部連合大会, Nov. 2009, Japanese, 電気関係学会関西支部, 吹田市, Domestic conference

  Poster presentation

• 独立頂点集合の抽出による最大重みクリークの上界計算法

  Masayuki NAKAMURA, Kazuaki YAMAGUCHI, Sumio MASUDA

  平成21年電気関係学会関西支部連合大会, Nov. 2009, Japanese, 電気関係学会関西支部, 吹田市, Domestic conference

  Poster presentation

• グラフの階層的直交描画アルゴリズムの改良

  Tetsuya Araki, Sumio Masuda, Kazuaki Yamaguchi

  平成21年電気関係学会関西支部連合大会, Nov. 2009, Japanese, 電気関係学会関西支部, 吹田市, Domestic conference

  Poster presentation

• 頂点とラベルの重なりを許した場合のグラフ描画における頂点ラベル配置法

  Noboru Abe, Sumio Masuda, Kazuaki Yamaguchi

  平成21年度情報処理学会関西支部支部大会, Sep. 2009, Japanese, 情報処理学会関西支部, 神戸市, Domestic conference

  Oral presentation

• 点パターン検索のためのアルゴリズムの提案

  MATSUDA Koji, NAKAMURA Masayuki, YAMAGUCHI Kazuaki, MASUDA Sumio

  第71回情報処理学会全国大会, Mar. 2009, Japanese, 情報処理学会全国大会, 滋賀県草津市, Domestic conference

  Oral presentation

• 文字列の縦書きと折り返しを許したラベル配置アルゴリズムへのシフト操作の導入

  KAWABATA Daiki, MASUDA Sumio, YAMAGUCHI Kazuaki

  平成20年電気関係学会関西支部連合大会, Nov. 2008, Japanese, 電気関係6学会関西支部, 京都市, Domestic conference

  Oral presentation

• 二次元点パターンマッチング問題に対する高速な確率アルゴリズムの提案

  SHINOHARA Takahiro, YAMAGUCHI Kazuaki, MASUDA Sumio

  平成20年電気関係学会関西支部連合大会, Nov. 2008, Japanese, 電気関係6学会関西支部, 京都市, Domestic conference

  Oral presentation

• 階層グラフ描画アルゴリズムにおける辺の形状の決定法

  ARAKI Tetsuya, MASUDA Sumio, YAMAGUCHI Kazuaki

  平成20年電気関係学会関西支部連合大会, Nov. 2008, Japanese, 電気関係6学会関西支部, 京都市, Domestic conference

  Oral presentation

• ラベル位置の敬遠度を導入した地図ラベル配置アルゴリズム

  KOMATSU Hiroaki, YAMAGUCHI Kazuaki, MASUDA Sumio

  平成20年電気関係学会関西支部連合大会, Nov. 2008, Japanese, 電気関係6学会関西支部, 京都市, Domestic conference

  Oral presentation

• Proposals of two approximation algorithms for the maximum weight clique problem

  FUJIWARA Masayasu, SHIBATA Kazunori, YAMAGUCHI Kazuaki, MASUDA Sumio

  平成20年度情報処理学会関西支部支部大会, Oct. 2008, Japanese, 情報処理学会関西支部, 京都市, Domestic conference

  Oral presentation

• A proposal of image search method based on the similarity of shapes and the performance evaluation of the system

  KOMOTO Satoshi, MATSUDA Koji, YAMAGUCHI Kazuaki, MASUDA Sumio

  平成20年度情報処理学会関西支部支部大会, Oct. 2008, Japanese, 情報処理学会関西支部, 京都市, Domestic conference

  Oral presentation

• Label size maximization for the vertices in a graph drawing

  ABE Noboru, MASUDA Sumio, YAMAGUCHI Kazuaki

  平成20年度情報処理学会関西支部支部大会, Oct. 2008, Japanese, 情報処理学会関西支部, 京都市, Domestic conference

  Oral presentation

• 有向グラフ描画アルゴリズムにおける閉路削除法の改良

  寺本 正幸, 増田 澄男, 山口 一章

  2008年電子情報通信学会総合大会, Mar. 2008, Japanese, 電子情報通信学会, 北九州市, Domestic conference

  Oral presentation

• 最大重みクリーク問題に対する貪欲アルゴリズムの提案

  吉川 聡司, 山口 一章, 増田 澄男

  平成19年電気関係学会関西支部連合大会, Nov. 2007, Japanese, 電気関係6学会関西支部, 神戸市, Domestic conference

  Oral presentation

• 階層的グラフにおける交差数最小化問題に対する局所探索法の適用

  田守 健太郎, 山口 一章, 増田 澄男

  平成19年電気関係学会関西支部連合大会, Nov. 2007, Japanese, 電気関係6学会関西支部, 神戸市, Domestic conference

  Oral presentation

• ラベルサイズ最大化問題の一般化とアルゴリズムの提案

  西山 岳史, 増田 澄男, 山口 一章

  平成19年電気関係学会関西支部連合大会, Nov. 2007, Japanese, 電気関係6学会関西支部, 神戸市, Domestic conference

  Oral presentation

• グラフ描画の直交格子への埋め込みアルゴリズムとデフォルメ路線図への応用

  橘 一行, 増田 澄男, 山口 一章

  平成19年電気関係学会関西支部連合大会, Nov. 2007, Japanese, 電気関係6学会関西支部, 神戸市, Domestic conference

  Oral presentation

• 2頂点間の最短経路問題における効率的な探索のための始点・終点の決定法

  藤原 正康, 山口 一章, 増田 澄男

  平成19年電気関係学会関西支部連合大会, Nov. 2007, Japanese, 電気関係6学会関西支部, 神戸市, Domestic conference

  Oral presentation

• 二次元点パターンマッチング問題に対する高速なアルゴリズム

  篠原 高広, Kazuaki YAMAGUCHI, Sumio MASUDA

  2007年電子情報通信学会総合大会, Mar. 2007, Japanese, Domestic conference

  Oral presentation

• 地図中の地点と線情報へのラベル配置のためのラベル候補作成法

  Noboru ABE, Masahiko KUSAKI, Sumio MASUDA, Kazuaki YAMAGUCHI

  2007年電子情報通信学会総合大会, Mar. 2007, Japanese, Domestic conference

  Oral presentation

• 図形データの重なり判定を高速化するデータ構造の提案

  三木 洋平, Kazuaki YAMAGUCHI, Sumio MASUDA

  2007年電子情報通信学会総合大会, Mar. 2007, Japanese, Domestic conference

  Oral presentation

• 引出し線を用いたラベル配置アルゴリズムの改良

  礒村 陽介, Sumio MASUDA, Kazuaki Yamaguchi

  2007年電子情報通信学会総合大会, Mar. 2007, Japanese, Domestic conference

  Oral presentation

• 頂点及び辺の付加に伴うグラフ描画の更新法

  長野 尚史, Sumio MASUDA, Kazuaki Yamaguchi

  平成18年電気関係学会関西支部連合大会, Nov. 2006, Japanese, Domestic conference

  Oral presentation

• 地点と領域に対するラベル配置アルゴリズム

  高橋 知裕, Kazuaki YAMAGUCHI, Sumio MASUDA

  平成18年電気関係学会関西支部連合大会, Nov. 2006, Japanese, Domestic conference

  Oral presentation

• 画像の形状を比較する方法の一提案

  岩田 香代, Kazuaki YAMAGUCHI, Sumio MASUDA

  平成18年電気関係学会関西支部連合大会, Nov. 2006, Japanese, Domestic conference

  Oral presentation

• グラフ描画アルゴリズムにおける頂点移動方法の改良

  上田 晃平, Sumio MASUDA, Kazuaki Yamaguchi

  平成18年電気関係学会関西支部連合大会, Nov. 2006, Japanese, Domestic conference

  Oral presentation

• グラフの変形操作による最大重みクリークの重みの上界計算法

  頭師 賢太郎, Kazuaki YAMAGUCHI, Sumio MASUDA

  平成18年電気関係学会関西支部連合大会, Nov. 2006, Japanese, Domestic conference

  Oral presentation

• ラベル配置問題の厳密解法の提案

  井上 裕一, Kazuaki YAMAGUCHI, Sumio MASUDA

  電子情報通信学会コンピュテーション研究会, Apr. 2006, Japanese, Domestic conference

  Oral presentation

• 優先度付き地図ラベル配置アルゴリズムの改良

  ABE Noboru, HATTORI Shuji, MASUDA Sumio, YAMAGUCHI Kazuaki

  電子情報通信学会総合大会, Mar. 2006, Japanese, 電子情報通信学会, 国士舘大学, Domestic conference

  Oral presentation

• 文字列の折り返しと縦書きを許す場合の地図ラベル配置アルゴリズム

  WAKITA Yuuji, MASUDA Sumio, YAMAGUCHI Kazuaki

  電気関係学会関西支部連合大会, Nov. 2005, Japanese, 電子情報通信学会, 京都大学, Domestic conference

  Oral presentation

• 地図中の地点と線情報に対するラベル配置アルゴリズム

  KUSAKI Masahiko, MASUDA Sumio, YAMAGUCHI Kazuaki

  電気関係学会関西支部連合大会, Nov. 2005, Japanese, 電子情報通信学会, 京都大学, Domestic conference

  Oral presentation

• 最大重みクリークを効率良く抽出するための頂点系列の生成法

  YAMAGUCHI Kazuaki, MASUDA Sumio

  電子情報通信学会コンピューテーション研究会, Sep. 2005, Japanese, 電子情報通信学会, 大阪大学, Domestic conference

  Oral presentation

• 最大重みクリークの重みの上界の高速な計算法

  YAMAGUCHI Kazuaki, MASUDA Sumio

  電子情報通信学会技術研究報告, Apr. 2005, Japanese, 電子情報通信学会, 関西学院大学, Domestic conference

  Oral presentation

• 分数彩色を用いた最大クリーク問題の近似解法

  頭師 賢太郎, 山口 一章, 増田 澄男

  電子情報通信学会関西支部第10回学生会研究発表会講演会, Mar. 2005, Japanese, 電子情報通信学会関西支部学生会, 未記入, Domestic conference

  Oral presentation

• 類似検索手法TLAESAの改良

  所 憲, 山口 一章, 増田 澄男

  2005年電子情報通信学会総合大会, 2005, Japanese, 電子情報通信学会, 大阪大学 豊中キャンパス, Domestic conference

  Oral presentation

• 優先度付き地図ラベル配置問題に関するラベル候補作成法

  阿部 昇, 増田 澄男, 山口 一章

  2005年電子情報通信学会総合大会, 2005, Japanese, 電子情報通信学会, 大阪大学 豊中キャンパス, Domestic conference

  Oral presentation

• 頂点がグループ分けされた階層的グラフの描画法

  阪本 聡良, 増田 澄男, 山口 一章

  2005年電子情報通信学会総合大会, 2005, Japanese, 電子情報通信学会, 大阪大学 豊中キャンパス, Domestic conference

  Oral presentation

• 地理データに対する領域管理手法の実験的評価

  熊野 達夫, 山口 一章, 増田 澄男

  2005年電子情報通信学会総合大会, 2005, Japanese, 電子情報通信学会, 大阪大学 豊中キャンパス, Domestic conference

  Oral presentation

• 候補の絞り込みによる画像検索手法の高速化

  岩田 香代, 山口 一章, 増田 澄男

  電子情報通信学会関西支部第10回学生会研究発表会講演会, 2005, Japanese, 電子情報通信学会関西支部学生会, 未記入, Domestic conference

  Oral presentation

• 引出し線を用いた地図ラベル配置アルゴリズム

  大森 和貴, 増田 澄男, 山口 一章

  電子情報通信学会コンピュテーション研究会, 2005, Japanese, 電子情報通信学会, 未記入, Domestic conference

  Oral presentation

• グラフ描画アルゴリズムに基づいたデフォルメ路線図作成法

  浅田 信浩, 増田 澄男, 山口 一章

  2005年電子情報通信学会総合大会, 2005, Japanese, 電子情報通信学会, 大阪大学 豊中キャンパス, Domestic conference

  Oral presentation

• グラフ描画アルゴリズムにおける頂点移動方法の改良

  上田 晃平, 増田 澄男, 山口 一章

  電子情報通信学会関西支部第10回学生会研究発表会講演会, 2005, Japanese, 電子情報通信学会関西支部学生会, 未記入, Domestic conference

  Oral presentation

• 複数の位置からの頂点移動を行うグラフ描画アルゴリズム

  山田 岳志, 増田 澄男, 山口 一章

  平成16年電気関係学会関西支部連合大会, 2004, Japanese, 情報処理学会関西支部, 大阪大学中之島センター, Domestic conference

  Oral presentation

• 二次元点パターンマッチング問題に対する一手法の提案

  伊吉 邦章, 山口 一章, 増田 澄男

  平成16年電気関係学会関西支部連合大会, 2004, Japanese, 情報処理学会関西支部, 大阪大学中之島センター, Domestic conference

  Oral presentation

• 点パターンマッチングを用いた画像検索法に関する一考察

  服部 克征, 山口 一章, 増田 澄男

  情報処理学会第66回全国大会, 2004, Japanese, 情報処理学会, 慶應義塾大学, Domestic conference

  Oral presentation

• 地点の消去を許す場合の地図ラベル配置アルゴリズム

  舟川 国男, 阿部 昇, 山口 一章, 増田 澄男

  平成16年度情報処理学会関西支部大会, 2004, Japanese, 情報処理学会関西支部, 大阪大学中之島センター, Domestic conference

  Oral presentation

• グラフの構造の簡略化による最短経路探索問題の解法の高速化

  牟禮 幸雄, 山口 一章, 増田 澄男

  平成16年電気関係学会関西支部連合大会, 2004, Japanese, 情報処理学会関西支部, 大阪大学中之島センター, Domestic conference

  Oral presentation

• Comparability supergraph を用いた最大重みクリーク問題の厳密解法

  山口 一章, 榊原 芳恵, 増田 澄男

  電子情報通信学会コンピュテーション研究会, 2004, Japanese, 電子情報通信学会, 未記入, Domestic conference

  Oral presentation

• Comparability subgraph の抽出に関する一考察

  榊原 芳江, 山口 一章, 増田 澄男

  平成16年電気関係学会関西支部連合大会, 2004, Japanese, 情報処理学会関西支部, 大阪大学中之島センター, Domestic conference

  Oral presentation

• 頂点がラベルをもつグラフの描画アルゴリズム

  阿部 昇, 増田 澄男, 山口 一章

  情報処理学会第65回全国大会, 2003, Japanese, 情報処理学会, 東京工科大学, Domestic conference

  Others

• 地名配置におけるラベル候補作成法

  阿部 昇, 舟川 国男, 増田 澄男, 山口 一章

  平成15年電気関係学会関西支部連合大会, 2003, Japanese, 電気学会関西支部, 大阪市立大学, Domestic conference

  Oral presentation

• 相似三角形による２次元パターンマッチングアルゴリズムに関する研究

  伊吉 邦章, 山口 一章, 増田 澄男

  電子情報通信学会関西支部学生研究発表会, 2003, Japanese, 電子情報通信学会 関西支部 学生会, 未記入, Domestic conference

  Others

• 重ね合わせコストによる画像検索の一手法

  関本 雅史, 榊原 芳恵, 山口 一章, 増田 澄男

  平成15年電気関係学会関西支部連合大会, 2003, Japanese, 電気学会関西支部, 大阪市立大学, Domestic conference

  Oral presentation

• 手書き画像を用いた類似画像検索法に関する一考察

  榊原 芳恵, 関本 雅史, 山口 一章, 増田 澄男

  平成15年電気関係学会関西支部連合大会, 2003, Japanese, 電気学会関西支部, 大阪市立大学, Domestic conference

  Oral presentation

• 引出し線の使用を許したラベル配置アルゴリズム

  大森 和貴, 増田 澄男, 山口 一章

  平成15年電気関係学会関西支部連合大会, 2003, Japanese, 電気学会, 未記入, Domestic conference

  Oral presentation

• グラフ描画への頂点ラベル及び辺ラベルの配置

  阿部 昇, 増田 澄男, 山口 一章

  平成15年電気関係学会関西支部連合大会, 2003, Japanese, 電気学会関西支部, 大阪市立大学, Domestic conference

  Oral presentation

• chordal supergraph と chordal subgraphによる最大クリーク問題の緩和問題構成法について

  西出 知史, 山口 一章, 増田 澄男

  電子情報通信学会コンピュテーション研究会, 2003, Japanese, 電子情報通信学会 コンピュテーション研究会, 未記入, Domestic conference

  Others

• A New Method to Obtain Relaxed Problems of Graph Optimization Problems

  YAMAGUCHI Kazuaki, TANAKA Hatsukazu, NISHIDE Tomofumi

  SIAM conf.on Computational Science and Engineering, 2003, English, 未記入, 未記入, Domestic conference

  Others

• A Lagrangian-relaxation based algorithm for calculating an upper bound of the size of the maximum cliques of grpahs.

  YAMAGUCHI Kazuaki, MASUDA Sumio

  5th International Congress on Industrial and Applied Mathematics., 2003, English, 未記入, Sydney, Australia, International conference

  Oral presentation

Association Memberships

• 電子情報通信学会

  Apr. 1995 - Present

• The Operations Research Society of Japan

  - Present

• Society for Industrial and Applied Mathematics

  - Present

• IEEE

  - Present

• 日本応用数理学会

  - Present

• 情報処理学会

  - Present

Research Projects

• DEVELOPMENT OF ALGORITHMS FOR FINDING AN ORTHOGONAL DRAWING OF A HIERARCHICAL GRAPH

  MASUDA SUMIO, YAMAGUCHI Kazuaki

  Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C), Grant-in-Aid for Scientific Research (C), Kobe University, 01 Apr. 2012 - 31 Mar. 2015

  In this research, we have presented algorithms for finding an orthogonal drawing of a hierarchical graph. In an orthogonal drawing, each edge is drawn as a path consisting of vertical and horizontal line segments. The proposed algorithms include the following methods: (i) an algorithm for sharing dummy vertices, (ii) a method for creating hyperedges from the set of edges of the resultant graph, (iii) a method for determining the x-coordinates of the vertices so that the total sum of the lengths of horizontal line segments becomes small, and (iv) an algorithm for drawing hyperedges. The last algorithm (iv) uses at most two horizontal line segments to draw each hyperedge and can make the number of edge crossings in the graph drawing small.

• INFORMATION VISUALIZATION BY GRAPH DRAWING ALGORITHMS

  MASUDA Sumio, YAMAGUCHI Kazuaki

  Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C), Grant-in-Aid for Scientific Research (C), Kobe University, 2009 - 2011

  In order to make graph drawing algorithms more effective for information visualization, we have developed the following algorithms :(1) an algorithm for producing an orthogonal drawing of a graph that basically preserves the relative vertex positions in a given straight-line drawing,(2) an algorithm for improving the quality of a straight-line drawing of a graph,(3) algorithms for determining the vertex coordinates and for sharing dummy vertices in a hierarchical graph drawing,(4) a force-oriented algorithm for drawing a disconnected graph, and(5) an algorithm for finding a graph drawing with rectangular vertices.

• DESIGN OF ALGORITHMS FOR FINDING A HIERARCHICAL DRAWING OF A DIRECTED GRAPH

  MASUDA SUMIO, YAMAGUCHI Kazuaki

  Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C), Grant-in-Aid for Scientific Research (C), Kobe University, 2007 - 2008

  代表的な有向グラフ描画法として, 階層的描画を求めるSugiyamaらの方法が知られている. 本研究では, この方法の各ステップについて考察し, 従来の方法の改良を行った. また, 辺交差数と描画幅削減のため, 垂直・水平線分のみを用いて辺を描く方法を開発した. さらに, 頂点がラベルをもつグラフに対して, グラフ描画を求めた後, できるだけ大きな文字サイズを使ってラベルを配置する方法を提案した.

• 図形アルファベット仮説に基づく画像検索・分類システムの開発

  山口 一章

  2007, Principal investigator

  Competitive research funding