Efficient Algorithms for Partitionings, Colorings and Drawings of Graphs and their Applications

高效的图形划分、着色和绘图算法及其应用

• 批准号: 21500001
• 负责人: NISHIZEKI Takao
• 金额: $ 2.91万
• 依托单位: Kwansei Gakuin University (2010-2013)Tohoku University (2009)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2009
• 资助国家: 日本
• 起止时间: 2009-04-01 至 2014-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-21500001/
• 关键词: グラフ; アルゴリズム; 分割; 彩色; 描画; 全域配送林; 直並列グラフ; 部分k木; 公平連結分割; 辺容量; 擬多項式時間; グラフ分割; グラフ彩色; グラフ描画; 格子凸描画; 内部3連結グラフ; 3連結成分分解木; アルゴリズム理論; 離散構造; 設計自動化; VLSI設計

This research develops efficient algorithms for the partitioning, coloring and drawing problems of graphs, and applies them to practical problems in real world. One of the representative results is an algorithm for the fairest connected partition problem. It partitions a weighted graph G to a specified number of connected subgraphs by deleting edges from G so that the difference between the maximum sum of weights in a subgraph and the minimum one is as small as possible.

这项研究开发了用于分区，着色和绘制图形问题的有效算法，并将其应用于现实世界中的实际问题。代表性结果之一是最公平的连接分区问题的算法。它通过从G中删除边缘将加权图G分配到指定数量的连接子图，从而使子图中的最大权重和最小值的最大权重总和之间的差异尽可能小。

项目成果

Convex drawings of internally triconnected plane graphs on O(n^2) grids

O(n^2) 网格上内部三联平面图的凸图

• 发表时间: 2010
• 期刊: Discrete Math., Alg.and Appl.
• 作者: Shuji Isobe;Eisuke Koizumi;Yuji Nishigaki;Hiroki Shizuya;X.Zhou
• 通讯作者: X.Zhou

直並列グラフの全域配送木

串并联图的全局分布树

• 作者: Y Inoue;A Matsumuro;M Hirose;T Arai;J Otsuka;C Sugimoto;S Minamoto;A Nishiyama;K Sugiyama;M Nakagawa;M Kitaichi;M Akira;S Hayashi;K Nakata;M Okada;and M Sakatani;對木悟;T. Nishizeki
• 通讯作者: T. Nishizeki

Small grid drawings of planar graphs with balanced bipartition

平衡二分平面图的小网格图

• 发表时间: 2010
• 作者: X.Zhou;T.Hikino;T.Nishizeki
• 通讯作者: T.Nishizeki

Absolutely secure message transmission using a key sharing graph-Extended Abstract-

使用密钥共享图实现绝对安全的消息传输-扩展摘要-

• 发表时间: 2011
• 作者: Y.Indo;T.Mizuki;T.Nishizeki
• 通讯作者: T.Nishizeki

Partitioning trees with supply, demand and edge-capacity-Extended Absutract-

用供给、需求和边缘容量来划分树-扩展抽象-

• 发表时间: 2011
• 作者: M.Kawabata;T.Nishizeki
• 通讯作者: T.Nishizeki