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

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

基本信息

批准号：
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>)の近似精度を持つ多項式時間アルゴリズムを示した.

这项研究的目的是，使用一组简单模式生成复杂模式的过程被正式定义为计算问题，从算法理论和计算数量中讨论，并且有一个必要的问题。并通过数学和智能绘制图形来开发具有质量和性能的近似算法。模式是今年的考试及其研究结果的以下内容。，以便可以将其作为面向图的问题。仙人掌的最低级超级类是困难的，而在P_42截面图的情况下，这是最小的仙人掌，很难拥有弱的NP，无钻石图，无房子，图2.2尺寸n×n网格是水平和垂直黑线的复杂模式，作为一个简单的模式，给出了2.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：
发表时间：
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，宮野英次