A study on Connectivity of Graphs and Its Applications

The subject of this research project is to promote research on connectivity of graphs and its applications。More precisely，theoretical characterization and design of algorithms，with emphasis on practical usefulness，concerning the following three major fields：Analysis(Detecting Connectivity Of Given Graphs)，Extraction(Extracting Subgraphs Having Prescribed Connectivity)，and Construction(Constructing Graphs With Given Connectivity)。Designing online and/or parallel/distributed algorithms is also included。The main achievements of this year are as follows.I.Holding two research seminars focusing on introducing new problems as well as how to solve open problems.·[At Hiroshima University，from 26 to 28 January 2004]The following leading researchers on connectivity participated the seminar：Prof.Andras Frank and Prof.Tibor Jordan from Eotvos Lorand University，Hungary，Prof.Takao Nishizeki of Tohoku University，Prof.Hiroshi Nagamochi and Prof.Toshimasa Ishii of Toyohashi Universi…More ty of Technology.In addition，one researcher in Hungary and four researchers in Japan attended。·[At Hiroshima University，from2to4 February 2005]The following leading researchers on connectivity participated the seminar：Prof.Andras Frank and Prof.Tibor Jordan from Eotvos Lorand University，Hungary，Prof.Hiroshi Nagamochi and Prof.Hiro Ito of Kyoto University，Prof.Kazuhisa Makino of Osaka University，Prof.Toshiya Mashima of Hiroshima International University.II.Publms the foling 25f.(2)2papers on fast and sharp approximation algorithms for connectivity augmentation problems for the edge-weighted case。(3)7papers on fast and sharp heuristic algorithms for constructing connected subgraphs satisfying certain conditions；(4)One paper on a fast algorithm for extracting planar subgraphs；2 Concerning“Designing online or distributed algorithms”：(1)2papers on parallel algorithms for extracting planar subgraphs；(2)2papers on searching paths in graphs；(3)4papers on paralleithms for extracting planar subgraphs；(2)2papers on searching paths in graphs；(3)4papers on paralleithms for constructing connected subgraphs。Less：Less

The subject of this research project is to promote research on connectivity of graphs and its applications. More precisely, theoretical characterization and design of algorithms, with emphasis on practical usefulness, concerning the following three major fields : Analysis (detecting connectivity of given graphs), Extraction (extracting subgraphs having prescribed connectivity), and Construction (constructing graphs with given connectivity). Designing online and/or parallel/distributed algorithms is also included. The main achievements of this year are as follows.I.Holding two research seminars focusing on introducing new problems as well as how to solve open problems.・[At Hiroshima University, from 26 to 28 January 2004] The following leading researchers on connectivity participated the seminar : Prof.Andras Frank and Prof.Tibor Jordan from Eotvos Lorand University, Hungary, Prof.Takao Nishizeki of Tohoku University, Prof.Hiroshi Nagamochi and Prof.Toshimasa Ishii of Toyohashi Universi … More ty of Technology. In addition, one researcher in Hungary and four researchers in Japan attended.・[At Hiroshima University, from 2 to 4 February 2005] The following leading researchers on connectivity participated the seminar : Prof.Andras Frank and Prof.Tibor Jordan from Eotvos Lorand University, Hungary, Prof.Hiroshi Nagamochi and Prof.Hiro Ito of Kyoto University, Prof.Kazuhisa Makino of Osaka University, Prof.Toshiya Mashima of Hiroshima International University.II.Publication of the following 25 research papers.1 Concerning "Construction" : (1)7 papers on connectivity augmentation problems for graphs in which each vertex has an upper bound on vertex-degree ; (2)2 papers on fast and sharp approximation algorithms for connectivity augmentation problems for the edge-weighted case. (3)7 papers on fast and sharp heuristic algorithms for constructing connected subgraphs satisfying certain conditions ; (4)One paper on a fast algorithm for extracting planar subgraphs ;2 Concerning "Designing online or distributed algorithms" : (1)2 papers on parallel algorithms for extracting planar subgraphs ; (2)2 papers on searching paths in graphs ; (3)4 papers on parallel/distributed branch-and-bound algorithms. Less