权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

アルゴリズム的グラフマイナー理論

算法图小理论

基本信息

批准号：
21650004
负责人：
河原林健一
金额：
$ 1.66万
依托单位：
National Institute of Informatics
依托单位国家：
日本
项目类别：
Grant-in-Aid for Challenging Exploratory Research
财政年份：
2009
资助国家：
日本
起止时间：
2009 至 2010
项目状态：
已结题

项目摘要

本年度は,主にセパレイターを研究した.1970年代にLIPTON-TARJANによって導入された平面グラフのセパレイターは,その後,グラフアルゴリズム分野の強力なツールとなった.例えば,平面ネットワーク上の最短パス問題などは,セパレイターの性質によるところが大きい全てのグラフがセパレイターを持つとは限らない,例えば,Expanderグラフや,密なグラフなどは,セパレイターがないことが知られている.したがってセパレイターが存在するグラフ族はなにか?という問題が,過去30年間調べられている.そして近年になって,最終的には,マイナーに関して閉じているグラフ族がセパレイターをもつある種の「限界」のグラフ族だと結論付けられているマイナーに関して閉じているグラフ族に関しては,Alon-Seymour-Thomasによる有名な結果(J.AMS&STOC'90)が知られている.彼らは,その論文の中で,具体的なセパレイターのサイズを予想した.この予想は,過去20年間でもセパレイターに関して最も注目された予想であり,いくつもの部分的結果が発表されてきた2010年度,B.Reed氏との共同研究で,この予想を完全解決した.論文は,理論計算機分野で最も権威がある国際会議であるFOCS (Annual Symposium on Foundations of Computer Science)に採択され,この会議の特集号に招待された

This year, the main focus of the study was on the introduction of LIPTON-TARJAN in the 1970s. After the introduction of LIPTON-TARJAN in the 1970s, the introduction of LIPTON-TARJAN in the 1970s was carried out. For example, the shortest distance problem on the flat surface is: reverse, reverse. The family has a lot of problems. The problem is that over the past 30 years, we've been working on it. In recent years, the final result of the study is that the Alon-Seymour-Thomas family has a well-known result (J.AMS&STOC'90). In the paper, the author thinks about the concrete problems. The results of this research in the past 20 years have been reported. In 2010,B.Reed's joint research has completely solved this problem. FOCS (Annual Symposium on Foundations of Computer Science) was held in Beijing from 1998 to 1999.

项目成果

期刊论文数量（0）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

The disjoint paths problem, structure and algorithm

不相交路径问题、结构和算法

DOI：
发表时间：
2009
期刊：
影响因子：
0
作者：
T.Kaneko;et al.;K. Kawarabayashi
通讯作者：
K. Kawarabayashi

Algorithms for finding an induced cycle in planar graphs

DOI：
10.1007/s00493-010-2499-x
发表时间：
2010-11
期刊：
Combinatorica
影响因子：
1.1
作者：
K. Kawarabayashi;Yusuke Kobayashi
通讯作者：
K. Kawarabayashi;Yusuke Kobayashi

Decomposing planar graphs of girth five into an independent set and a forest

将周长五的平面图分解为独立集和森林

DOI：
发表时间：
2009
期刊：
J.Combin.Theory Ser.B 99
影响因子：
0
作者：
T. Nagakura;T. Hosokawa;& K. Omukai;K.Kawarabayashi;丸藤亜寿紗;H. Hirashita & K. Omukai;K.Kawarabayashi et al.
通讯作者：
K.Kawarabayashi et al.

Removable cycles in non-bipartite graphs

非二部图中的可移除循环

DOI：
发表时间：
2009
期刊：
J.Combin.Theory Ser.B 99
影响因子：
0
作者：
Omura;K.;Okada;N.;K.Ando et al.;K.Kawarabayashi et al.
通讯作者：
K.Kawarabayashi et al.

Algorithmic Graph Minor Theory : Improved Grid Minor Bounds and Wagner's Contraction

算法图小理论：改进的网格小界限和瓦格纳收缩

DOI：
发表时间：
2006
期刊：
Proceedings of The 17th International Symposium on Algorithms and Computation LNCS4288
影响因子：
0
作者：
E.D.Demaine;M.Hajiaghayi;K.Kawarabayashi
通讯作者：
K.Kawarabayashi