単純パターンを用いた複雑パターン生成アルゴリズムとその計算複雑さ

使用简单模式的复杂模式生成算法及其计算复杂度

基本信息

批准号：
17700022
负责人：
宮野英次
金额：
$ 1.92万
依托单位：
Kyushu Institute of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Young Scientists (B)
财政年份：
2005
资助国家：
日本
起止时间：
2005 至 2007
项目状态：
已结题

项目摘要

本研究の目標は,単純パターンの集合を用いて複雑パターンを生成するプロセスを計算問題として形式的に定義し,アルゴリズム論及び計算量理論的な観点から議論を行い,本問題が本質的に有する計算時間限界の解明と品質・性能保証された近似アルゴリズムの開発を行うことである.多くの場合に感覚的に議論されていた図形描画を,数学的・情報学的に議論することにより作業効率を計る尺度を明確にし,効率の良いアルゴリズム開発を目指す.本年度の検討事項とその研究成果は以下である.1.線画図形における複雑パターンを単純パターンにより生成する問題は,与えられた単純パターンを1つの頂点として,隣接する単純パターン間の関係を辺として無向グラフで表し,どの順番で生成するかという関係を辺の方向付けで表すことにより,グラフ有向化の問題として形式化できる.本年度は,最大出次数を最小化するグラフ有向化最適化問題について,入力グラフがカクタスの場合Pであること,カクタスの最小スーパークラスである外部平面グラフの場合弱NP困難であること,別のカクタスの最小スーパークラスであるP_42部グラフの場合弱NP困難であること,ダイヤモンドフリーグラフ,ハウスフリーグラフ,直並列グラフ,2部グラフ,平面グラフの場合にはいずれもNP困難となることを示した.2.2次元n×nメッシュ上に複雑パターンとして水平・垂直の黒線分が与えられ,単純パターンとして1×1タイルの4辺の白・黒線分の組み合わせが与えられた時の単純パターンによる複雑パターンの線画描画問題について,任意の複雑パターンを実現するための単純パターン集合の必要十分条件を示した.また,線画描画を最適化問題として定式化し,O((logn)^<1/2>)の近似精度を持つ多項式時間アルゴリズムを示した.

这项研究的目的是正式定义使用一组简单模式作为计算问题的复杂模式的过程，从算法理论和计算复杂性理论的角度进行讨论，并以保证的质量和性能开发近似算法。通过讨论经常在数学和信息学中直观讨论的地理图，我们旨在开发有效的算法。今年的考虑和研究结果如下：1。使用简单模式在线图中生成复杂模式的问题可以被形式化为图形指导，通过表达相邻的简单模式之间的关系为一个顶点，并通过表达相邻的简单模式（如边缘）之间的关系，并表达通过边缘方向生成顺序的关系。今年的目标是最大程度地减少最大结果顺序。 Regarding the F directed optimization problem, we have shown that the input graph is P when the input graph is cactus, the external plane graph, which is the smallest superclass of cactus, the weak NP is difficult, and that the P_42 part graph, which is the smallest superclass of another cactus, and that the NP is difficult in both diamond-free graphs, house-free graphs, serial parallel graphs, bipartite graphs, and planar图2。关于在水平和垂直黑线作为复杂模式时，使用简单模式的复杂模式的线图问题，以及将四个侧面的白色和黑色线组成1×1瓷砖，作为简单模式，简单的条件是简单的条件，用于实现任意模式的简单模式。我们还将线图作为优化问题，并显示了具有O（（（logN）^<1/2>）近似精度的多项式时间算法。

项目成果

期刊论文数量（0）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree

最小化最大加权出度的图方向近似算法

DOI：
10.1007/s10878-009-9276-z
发表时间：
2011
期刊：
J. Comb. Optim
影响因子：
0
作者：
Yuichi Asahiro;Jesper Jansson;Eiji Miyano;Hirotaka Ono;Kouhei Zenmyo
通讯作者：
Kouhei Zenmyo

DOI：
{{ item.doi }}
发表时间：
{{ item.publish_year }}
期刊：
{{ item.journal_name }}
影响因子：
{{ item.factor }}
作者：
{{ item.authors }}
通讯作者：
{{ item.author }}

数据更新时间：{{ journalArticles.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ monograph.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ sciAawards.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ conferencePapers.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ patent.updateTime }}

宮野英次其他文献

最大・最小支配ツアー問題の計算複雑さ

最大-最小支配旅游问题的计算复杂度

DOI：
发表时间：
2018
期刊：
影响因子：
0
作者：
朝廣雄一;Guohui Lin;Zhilong Liu;宮野英次;小林賢也，Guohui Lin，宮野英次，八木田剛;寺原一平，江藤宏，Guohui Lin，宮野英次;歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆;林田将敬，宮野英次;吉瀬紘平，宮野英次;税所航平，宮野英次;歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆;寺原一平，朝廣雄一，江藤宏，土中哲秀，Guohui Lin，宮野英次;小林賢也，Guohui Lin，宮野英次，八木田剛;朝廣雄一，ジャンソンジェスパー，宮野英次，小野廣隆，T.P.サディヤ;朝廣雄一，ジャンソンジェスパー，宮野英次，ニクパイヘサム，小野廣隆;江藤宏，土中哲秀，宮野英次，西島歩美，小野廣隆，大舘陽太，斎藤寿樹，上原隆平，ヴァンデルザンデントム;八木田剛，朝廣雄一，宮野英次;野々上夏葵，江藤宏，宮野英次
通讯作者：
野々上夏葵，江藤宏，宮野英次

重複無し最長共通部分列問題の計算時間

无重复的最长公共子序列问题的计算时间

DOI：
发表时间：
2019
期刊：
影响因子：
0
作者：
朝廣雄一;Guohui Lin;Zhilong Liu;宮野英次;小林賢也，Guohui Lin，宮野英次，八木田剛;寺原一平，江藤宏，Guohui Lin，宮野英次;歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆;林田将敬，宮野英次;吉瀬紘平，宮野英次;税所航平，宮野英次;歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆
通讯作者：
歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆

最小ブロック転送問題について

关于最小块传输问题

DOI：
发表时间：
2018
期刊：
影响因子：
0
作者：
朝廣雄一;Guohui Lin;Zhilong Liu;宮野英次;小林賢也，Guohui Lin，宮野英次，八木田剛;寺原一平，江藤宏，Guohui Lin，宮野英次;歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆;林田将敬，宮野英次;吉瀬紘平，宮野英次;税所航平，宮野英次;歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆;寺原一平，朝廣雄一，江藤宏，土中哲秀，Guohui Lin，宮野英次;小林賢也，Guohui Lin，宮野英次，八木田剛;朝廣雄一，ジャンソンジェスパー，宮野英次，小野廣隆，T.P.サディヤ;朝廣雄一，ジャンソンジェスパー，宮野英次，ニクパイヘサム，小野廣隆;江藤宏，土中哲秀，宮野英次，西島歩美，小野廣隆，大舘陽太，斎藤寿樹，上原隆平，ヴァンデルザンデントム;八木田剛，朝廣雄一，宮野英次;野々上夏葵，江藤宏，宮野英次;柳植竜，朝廣雄一，Guohui Lin，宮野英次;寺原一平，江藤宏，Guohui Lin，宮野英次;小林賢也，Guohui Lin，宮野英次，斎藤寿樹，鈴木顕，八木田剛;八木田剛，朝廣雄一，宮野英次
通讯作者：
八木田剛，朝廣雄一，宮野英次

C5フリー正則グラフ上での誘導マッチング問題に対する近似アルゴリズム

C5自由正则图引导匹配问题的逼近算法

DOI：
发表时间：
2018
期刊：
影响因子：
0
作者：
朝廣雄一;Guohui Lin;Zhilong Liu;宮野英次;小林賢也，Guohui Lin，宮野英次，八木田剛;寺原一平，江藤宏，Guohui Lin，宮野英次;歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆;林田将敬，宮野英次;吉瀬紘平，宮野英次;税所航平，宮野英次;歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆;寺原一平，朝廣雄一，江藤宏，土中哲秀，Guohui Lin，宮野英次;小林賢也，Guohui Lin，宮野英次，八木田剛;朝廣雄一，ジャンソンジェスパー，宮野英次，小野廣隆，T.P.サディヤ;朝廣雄一，ジャンソンジェスパー，宮野英次，ニクパイヘサム，小野廣隆;江藤宏，土中哲秀，宮野英次，西島歩美，小野廣隆，大舘陽太，斎藤寿樹，上原隆平，ヴァンデルザンデントム;八木田剛，朝廣雄一，宮野英次;野々上夏葵，江藤宏，宮野英次;柳植竜，朝廣雄一，Guohui Lin，宮野英次
通讯作者：
柳植竜，朝廣雄一，Guohui Lin，宮野英次

ネットワークの同種親和性を定式化した最適化問題

制定网络同质性的优化问题

DOI：
发表时间：
2019
期刊：
影响因子：
0
作者：
朝廣雄一;Guohui Lin;Zhilong Liu;宮野英次;小林賢也，Guohui Lin，宮野英次，八木田剛;寺原一平，江藤宏，Guohui Lin，宮野英次;歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆;林田将敬，宮野英次;吉瀬紘平，宮野英次;税所航平，宮野英次;歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆;寺原一平，朝廣雄一，江藤宏，土中哲秀，Guohui Lin，宮野英次
通讯作者：
寺原一平，朝廣雄一，江藤宏，土中哲秀，Guohui Lin，宮野英次