Integrated Research on Connectivity of Graphs
Integrated Research on Connectivity of Graphs
批准号:
18500014
负责人:
WATANABE Toshimasa
金额:
$2.55万
依托单位:
依托单位国家:
日本
项目类别:
Grant-in-Aid for Scientific Research (C)
财政年份:
2006
资助国家:
日本
项目状态:
已结题
起止时间:
2006 至 2007
中文摘要
本项目的主题是促进关于图的连通性及其应用的理论刻画和设计实用算法的研究。研究结果(1)当每个顶点在顶点的度上有一个上混合度时,构造一个具有给定连通度的最小图(2006年和2007年各1篇论文)。(2)构造具有指定连通度的最小代价图的快速算法(2006年1篇论文)。(3)图的最大代价匹配铰链的快速算法(2006年1篇论文,2007年2篇论文)。(4)改变边权重后重建最短路径树的快速算法(2006年2篇论文)。(5)提取生成平面子图的夏普算法(2006年1篇论文(6)斯坦纳树的有效构造及其并行化(2006年和2007年各1篇论文)。(7)图着色的快速算法(2007年3篇)。(8)图的顶点覆盖的快速算法(2007年1篇)。(9)研究…更多关于Petri网(向量相加系统的具体模型)(2007年4篇论文)2.研究促进活动举办了两次关于图的连通性的研讨会(每个财政年度一个),并在广岛大学的Gakushi-Kaikan教授进行了演讲,随后在广岛大学的Gakushi-Kaikan教授进行了密集的讨论。[日期]:2007年1月31日-2月2日[参与者]:京都大学的Hiroshi Nagamochi教授、Hiro Ito教授和Talum Cum Fukunaga教授、东京大学的Kazuhisa Makino教授、广岛国际大学的Toshiya Mashima教授、广岛国际大学的Toshimasa Watanabe教授、Hiroma大学的Satoshi Taoka教授和Daisuke Takafuji教授Tibor Jordan教授和教授匈牙利Eotvos Lorand大学的Kiraly教授(2)[日期]:2008年3月10日-3月12日[参与者]:京都大学的Ito教授和Minim Fukunaga教授和Kannya Sugihara博士,东京大学的Kazuhisa Makino教授,Otaru商业大学的Toshimasa Ishii教授,广岛国际大学的Mashima教授,广岛大学的Toshimasa Watanabe教授,广岛大学的Satoshi Taoka教授和Daisuke Takafuji教授,匈牙利Eotvos Lorand大学的Thor Jordan教授和Kiraly教授
英文摘要
The subject of this project is to promote research on theoretical characterization and designing practical algorithms concerning connectivity of graphs and its applications.1. Research results(1) Constructing a minimum graph with presented connectivity when each vertex has an upper blend on vertex degree (1 paper in each of 2006 and 2007).(2) Sharp and fast algorithms for constructing a minimum-cost graph with prescribed connectivity (1 paper in 2006).(3) Fast algorithms for maximum-cost mate-hinge of graphs (1 paper in 2006 and 2 papers in 2007).(4) Fast algorithms for reconstructing shortest path tress after change in edge weights (2 papers in 2006).(5) Sharp algorithms for extracting spanning planar subgraphs (1 paper in 2006).(6) Efficient construction of Steiner trees and their parallelization (1 paper in each of 2006 and 2007).(7) Sharp and fast algorithms for graph coloring (3 papers in 2007).(8) Sharp and fast algorithms for vertex covers of graphs (1 Paper in 2007).(9) Resear … More ch on Petri nets (a concrete model of vector-addition systems)(4 papers in 2007)2. Research promoting activityHolding two workshop-type seminars (one for each fiscal year) on connectivity of graphs, with presentation followed by intensive discussion at Gakushi-Kaikan, Hiroshima University.(1) [Date]: January 31-February 2, 2007[Participants]: Prof Hiroshi Nagamochi, Prof Hiro Ito and Prof Talcum Fukunaga of Kyoto University, Prof Kazuhisa Makino of Tokyo University, Prof Toshiya Mashima of Hiroshima International University, Prof Toshimasa Watanabe, Prof Satoshi Taoka and Prof Daisuke Takafuji of Hiroshirma University, Prof Tibor Jordan and Prof Tam\as Kiraly of Eotvos Lorand University Hungary(2) [Date]: Mrch 10-March 12, 2008[Participants]: Prof Him Ito and Prof minim Fukunaga and Dr. Kannya Sugihara of Kyoto University, Prof Kazuhisa Makino of Tokyo University, Prof Toshimasa Ishii of Otaru University of Commerce, Prof Toshiya Mashima of Hiroshima International University Prof Toshimasa Watanabe, Prof Satoshi Taoka and Prof Daisuke Takafuji of Hiroshima University Prof Thor Jordan and Prof remits Kiraly of Eotvos Lorand University, Hungary Less
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
登录
查看更多内容
格子スタイナー木問題に対する領域分割に基づく並列解法
基于域分解的格子斯坦纳树问题并行求解方法
DOI:
--
发表时间:
2008
期刊:
影响因子:
--
作者:
[Keiichirou Kusakari, Masahiko Sakai, 江頭 一廣]
通讯作者:
江頭 一廣
DOI:
--
发表时间:
2008
期刊:
影响因子:
--
作者:
[Shinji, Okada]
通讯作者:
Okada
A Parallel Algorithm based on Area-Partitioning for the Rectilinear Steiner Problem
直线Steiner问题的基于区域划分的并行算法
DOI:
--
发表时间:
2008
期刊:
影响因子:
--
作者:
[Kazuhiro, Egashira]
通讯作者:
Egashira
Enhancing Stability of the Fourier Motzkin Method based on Siphon-trap Extraction of Petri nets
基于Petri网虹吸陷阱提取的Fourier Motzkin方法增强稳定性
DOI:
--
发表时间:
2007
期刊:
影响因子:
--
作者:
[Jose Iborra, Naoki Nishida, German Vidal, Tomohiro Chikada]
通讯作者:
Tomohiro Chikada
重み増加パス探索改良によるグラフ最大重みマッチング近似解法の性能強化
通过改进权重增加路径搜索增强图最大权重匹配近似求解方法的性能
DOI:
--
发表时间:
2007
期刊:
影响因子:
--
作者:
[西田直樹, 坂田翼, 酒井正彦, 草刈圭一朗, 坂部俊樹, 西河 恭倫]
通讯作者:
西河 恭倫
共 22 条
Integrated Research on Connectivity of Graphs and its Applications
-
批准号:20500015
-
项目类别:Grant-in-Aid for Scientific Research (C)
-
资助金额:$2.91万
-
财政年份:2008
-
负责人:WATANABE Toshimasa
-
依托单位:
A study on Connectivity of Graphs and Its Applications
-
批准号:15500011
-
项目类别:Grant-in-Aid for Scientific Research (C)
-
资助金额:$2.43万
-
财政年份:2003
-
负责人:WATANABE Toshimasa
-
依托单位:
ネットワーク最適化問題の解法効率化に関する研究
-
批准号:10205219
-
项目类别:Grant-in-Aid for Scientific Research on Priority Areas (B)
-
资助金额:$6.59万
-
财政年份:1998
-
负责人:WATANABE Toshimasa
-
依托单位: