Integrated Research on Connectivity of Graphs

本课题旨在推动图的连通性的理论表征和设计实用算法及其应用的研究。研究成果(1)构造一个顶点在顶点度上有一个上混合时具有连通的最小图（2006年和2007年各1篇）。(2)构造具有规定连通性的最小代价图的快速算法（2006年1篇论文）。(3)图的最大代价配对铰链快速算法（2006年1篇，2007年2篇）。(4)边权变化后重建最短路径树的快速算法（2006年2篇论文）。(5)生成平面子图提取的尖锐算法（2006年1篇论文）。(6) Steiner树的高效构造及其并行化（2006年和2007年各1篇）。(7)图形着色的快速锐利算法（2007年发表论文3篇）。(8)图顶点覆盖的快速锐利算法（1 Paper in 2007）。(9) Petri网（向量加法系统的一种具体模型）的研究（2007年4篇）研究促进活动在广岛大学Gakushi-Kaikan举办了两次关于图表连通性的讲习班式研讨会（每个财政年度一次），并在演讲后进行了深入讨论。(1)[日期]:2007年1月31日至2月2日[参与者]：京都大学永内博教授、伊藤宏教授、福永Talcum教授，东京大学牧野和久教授，广岛国际大学岛岛俊也教授，广岛大学渡边俊正教授、田冈聪教授、高路大辅教授，匈牙利Eotvos Lorand大学Tibor Jordan教授和Tam\as Kiraly教授(2)[日期]:2008年3月10日至3月12日[参与者]：京都大学伊藤谦教授、福永永教授、杉原健弥博士、东京大学牧野和久教授、小丸商业大学石井俊正教授、广岛国际大学岛岛俊也教授、渡边俊正教授、广岛大学田冈聪教授、高福大辅教授、托尔·乔丹教授、匈牙利罗兰大学基拉利教授

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