一个图G=(V,E)的树分解是将结点集V的子集作为树T的节点,使得在T上任意一条路径上的两个端节点的交集包含于该路径上的任意一个节点中。将T上最小(节点)对应子集的元素个数减1定义为分解树T的宽度,用宽度最小的分解树T的树宽度定义图G...一个图G=(V,E)的树分解是将结点集V的子集作为树T的节点,使得在T上任意一条路径上的两个端节点的交集包含于该路径上的任意一个节点中。将T上最小(节点)对应子集的元素个数减1定义为分解树T的宽度,用宽度最小的分解树T的树宽度定义图G的树宽度。一个合取范式(Conjunctive Normal Form,CNF)公式F可以用一个二分图G=(V∪C,E)表示(公式的因子图),其中变元结点集V对应公式F中的变元集,子句结点集C对应公式F中的子句集,变元在子句中的正(负)出现用实(虚)边表示。忽略公式因子图中边上的符号,得到一个二分图。文中研究了图的树分解算法,并将树分解算法应用到CNF公式的因子图树分解。通过实验观察公式因子图的树宽度与求解难度之间的联系。展开更多
Concepts of weak-quasi-bandwidth and forward-bandwidth of graphs are introduced. They are used to studythe following problems in graph theory: bandwidth, topological bandwidth, fill-in, profile, path-width, tree-width.
Many difficult (often NP-complete) optimization problems can be solved efficiently on graphs of small tree-width with a given tree-decomposition.In this paper,it is discussed how to solve the minimum feedback vertex s...Many difficult (often NP-complete) optimization problems can be solved efficiently on graphs of small tree-width with a given tree-decomposition.In this paper,it is discussed how to solve the minimum feedback vertex set problem and the minimum vertex feedback edge set problem efficiently by using dynamic programming on a tree-decomposition.展开更多
Latent Semantic Analysis involves natural language processing techniques for analyzing relationships between a set of documents and the terms they contain, by producing a set of concepts (related to the documents and ...Latent Semantic Analysis involves natural language processing techniques for analyzing relationships between a set of documents and the terms they contain, by producing a set of concepts (related to the documents and terms) called semantic topics. These semantic topics assist search engine users by providing leads to the more relevant document. We develope a novel algorithm called Latent Semantic Manifold (LSM) that can identify the semantic topics in the high-dimensional web data. The LSM algorithm is established upon the concepts of topology and probability. Asearch tool is also developed using the LSM algorithm. This search tool is deployed for two years at two sites in Taiwan: 1) Taipei Medical University Library, Taipei, and 2) Biomedical Engineering Laboratory, Institute of Biomedical Engineering, National Taiwan University, Taipei. We evaluate the effectiveness and efficiency of the LSM algorithm by comparing with other contemporary algorithms. The results show that the LSM algorithm outperforms compared with others. This algorithm can be used to enhance the functionality of currently available search engines.展开更多
Using seven well-replicated Qilian juniper (Sabina przewalskii Kom.) ring-width chronologies developed at Zongwulong and Shalike Mts. in the northeastern part of the Qaidam Basin annual precipitation from previous Jul...Using seven well-replicated Qilian juniper (Sabina przewalskii Kom.) ring-width chronologies developed at Zongwulong and Shalike Mts. in the northeastern part of the Qaidam Basin annual precipitation from previous July to current June in the recent 1000 years was re- constructed for Delingha. The reconstruction can capture 63.1% of precipitation variance and the equation was stable over time. For the reconstructed precipitation, wet periods occurred in AD1520—1633 and 1933—2001, whereas dry intervals in 1429—1519 and 1634—1741. In ad- dition, the magnitude in precipitation variation was lower before 1430 with about 15 mm, but it increased to 30 mm during the period of 1430 to 1850. After 1850, the precipitation variance de- creased again. In contrast to the increase in temperature, a decrease in annual precipitation was evident since the 1990s. The agreement in low-frequency variation between the reconstruction and the glacier accumulation and particulate content in Dunde ice cores during the recent several hundred years suggested that the precipitation reconstructed in this study was rather reliable, and represented a regional signal. This 1000-year reconstruction could benefit our understanding of climatic variation in decadal to century-scale in this region, and provide basic data to climate models and to prediction of future climate in the 21st century.展开更多
Based on the cross-dated tree-ring samples collected from the middle Qilian Moun- tain, a standard ring-width chronology had been developed, which covered the period AD 1000 to 2000. The correlations between the chron...Based on the cross-dated tree-ring samples collected from the middle Qilian Moun- tain, a standard ring-width chronology had been developed, which covered the period AD 1000 to 2000. The correlations between the chronology and climatic records from the nearby meteorological stations indicated that temperature was the dominant climatic factor for tree growth at upper timberline, and the most important climatic factor for the tree growth in the area was the mean temperature from previous December to current April. The temperature variations recovered from the ring-width data showed a cold period during the “Little Ice Age” and the con- tinuous warming during the twentieth century. Comparison between the ring-width chronology and δ18O records from the Dunde ice core in the Qilian Mountain indicated that there was a con- sistent trend in both time series. A significant correlation existed between our ring-width chro- nology and the Northern Hemispheric temperature, suggesting that the climate changes in the Qilian Mountain were not only driven by regional factors, but also responsive to the global cli- mate.展开更多
文摘一个图G=(V,E)的树分解是将结点集V的子集作为树T的节点,使得在T上任意一条路径上的两个端节点的交集包含于该路径上的任意一个节点中。将T上最小(节点)对应子集的元素个数减1定义为分解树T的宽度,用宽度最小的分解树T的树宽度定义图G的树宽度。一个合取范式(Conjunctive Normal Form,CNF)公式F可以用一个二分图G=(V∪C,E)表示(公式的因子图),其中变元结点集V对应公式F中的变元集,子句结点集C对应公式F中的子句集,变元在子句中的正(负)出现用实(虚)边表示。忽略公式因子图中边上的符号,得到一个二分图。文中研究了图的树分解算法,并将树分解算法应用到CNF公式的因子图树分解。通过实验观察公式因子图的树宽度与求解难度之间的联系。
文摘Concepts of weak-quasi-bandwidth and forward-bandwidth of graphs are introduced. They are used to studythe following problems in graph theory: bandwidth, topological bandwidth, fill-in, profile, path-width, tree-width.
基金Partially supported by the National Natural Science Foundation of China( 1 0 2 71 0 65
文摘Many difficult (often NP-complete) optimization problems can be solved efficiently on graphs of small tree-width with a given tree-decomposition.In this paper,it is discussed how to solve the minimum feedback vertex set problem and the minimum vertex feedback edge set problem efficiently by using dynamic programming on a tree-decomposition.
文摘Latent Semantic Analysis involves natural language processing techniques for analyzing relationships between a set of documents and the terms they contain, by producing a set of concepts (related to the documents and terms) called semantic topics. These semantic topics assist search engine users by providing leads to the more relevant document. We develope a novel algorithm called Latent Semantic Manifold (LSM) that can identify the semantic topics in the high-dimensional web data. The LSM algorithm is established upon the concepts of topology and probability. Asearch tool is also developed using the LSM algorithm. This search tool is deployed for two years at two sites in Taiwan: 1) Taipei Medical University Library, Taipei, and 2) Biomedical Engineering Laboratory, Institute of Biomedical Engineering, National Taiwan University, Taipei. We evaluate the effectiveness and efficiency of the LSM algorithm by comparing with other contemporary algorithms. The results show that the LSM algorithm outperforms compared with others. This algorithm can be used to enhance the functionality of currently available search engines.
基金the National KeyBasic Research Development Project of China(Grant No.19980408)the Key Project of Knowledge Innovation of the CAs(Grant No.KZcx2-314) the National Key Project of Science and Technology(Grant No.2001-BA611B-O1).
文摘Using seven well-replicated Qilian juniper (Sabina przewalskii Kom.) ring-width chronologies developed at Zongwulong and Shalike Mts. in the northeastern part of the Qaidam Basin annual precipitation from previous July to current June in the recent 1000 years was re- constructed for Delingha. The reconstruction can capture 63.1% of precipitation variance and the equation was stable over time. For the reconstructed precipitation, wet periods occurred in AD1520—1633 and 1933—2001, whereas dry intervals in 1429—1519 and 1634—1741. In ad- dition, the magnitude in precipitation variation was lower before 1430 with about 15 mm, but it increased to 30 mm during the period of 1430 to 1850. After 1850, the precipitation variance de- creased again. In contrast to the increase in temperature, a decrease in annual precipitation was evident since the 1990s. The agreement in low-frequency variation between the reconstruction and the glacier accumulation and particulate content in Dunde ice cores during the recent several hundred years suggested that the precipitation reconstructed in this study was rather reliable, and represented a regional signal. This 1000-year reconstruction could benefit our understanding of climatic variation in decadal to century-scale in this region, and provide basic data to climate models and to prediction of future climate in the 21st century.
基金supported by the Major Knowiedge Innovation Project of the Chinese Aademy of Sciences(Gant Nos.KZCX1-1002 and KZCX1-1009)the opening fund of the Key Laboratory of Ice-core and Cold-regions Environment,Cold and Arid Regions Environment and Engineering Research Insti tute,Chinese Academy ofSciences(Grant No.210506)..
文摘Based on the cross-dated tree-ring samples collected from the middle Qilian Moun- tain, a standard ring-width chronology had been developed, which covered the period AD 1000 to 2000. The correlations between the chronology and climatic records from the nearby meteorological stations indicated that temperature was the dominant climatic factor for tree growth at upper timberline, and the most important climatic factor for the tree growth in the area was the mean temperature from previous December to current April. The temperature variations recovered from the ring-width data showed a cold period during the “Little Ice Age” and the con- tinuous warming during the twentieth century. Comparison between the ring-width chronology and δ18O records from the Dunde ice core in the Qilian Mountain indicated that there was a con- sistent trend in both time series. A significant correlation existed between our ring-width chro- nology and the Northern Hemispheric temperature, suggesting that the climate changes in the Qilian Mountain were not only driven by regional factors, but also responsive to the global cli- mate.
