检索结果-内蒙古大学图书馆

A linear algorithm for semi-external cutnode computation

INFORMATION SCIENCES 2022年 615卷 368-384页

作者： Wan, Xiaolong Wang, Hongzhi Harbin Inst Technol Sch Comp Sci & Technol Harbin Peoples R China

In the literature, many algorithms have been proposed for finding cutnodes on undirected graphs, since cutnodes are crucial to graph connectivity. Here, a cutnode of an undirected graph G is a node of G, whose deletion will cause a reachable pair of the other nodes in G to be unreachable. Currently, the difficulty of maintaining the entire G in the main memory makes researchers pay attention to compute cutnodes on semi-external memory model. This paper shows that traditional semi-external algorithms are limited by their unbounded time and I/O consumption, making them impractical when G is relatively large or complex. Thus, we propose a linear semi -external cutnode computation algorithm, named SECN. Assuming that G has n nodes and m edges, and B is the disk block size. SECN is the first that can find all the cutnodes of G in O(m thorn n) time and with O(m/B) I/O cost on the semi-external memory model, as far as we know. SECN also has a smaller minimum memory space requirement than traditional algorithms. Our experimental evaluation conducted on both synthetic and real graphs confirms that SECN significantly outperforms existing algorithms (up to 103 times faster). (c) 2022 Elsevier Inc. All rights reserved.

关键词： Cutnode Semi-external memory Graph algorithm linear algorithm

来源：评论

学校读者我要写书评

暂无评论

Towards achieving online prediction of starch in postharvest sweet potato [Ipomoea batatas (L.) Lam] by NIR combined with linear algorithm

引用

JOURNAL OF FOOD COMPOSITION AND ANALYSIS 2023年第1期118卷

作者： He, Hong-Ju Wang, Yangyang Wang, Yuling Ou, Xingqi Liu, Hongjie Zhang, Mian Henan Inst Sci & Technol Sch Food Sci Xinxiang 453003 Peoples R China Nanyang Technol Univ Sch Chem Chem Engn & Biotechnol Singapore 637459 Singapore Henan Inst Sci & Technol Sch Life Sci & Technol Xinxiang 453003 Peoples R China Guangxi Univ Sch Chem & Chem Engn Nanning 530004 Peoples R China

Sweet potato [Ipomoea batatas (L.) Lam] is one of the primary sources for producing high-quality starch characterized by large particles and high viscosity, and has been widely used as suitable raw materials for industrial production purposes. To quantify the starch content in postharvest sweet potatoes for industrial application, an online method based on near-infrared (NIR) data combined with chemometrics was developed using 650 samples for calibration and internal validation, and 50 samples for independent external validation. Seven informative wavelengths (910, 959, 1197, 1215, 1450, 1468 and 1699 nm) associated with the prediction of starch in 900-1700 nm range were further selected by competitive adaptive reweighted sampling (CARS) algorithm to relate to measured starch values using linear algorithms, achieving good validation performance to predict starch of sweet potato with correlation coefficients of 0.94 and error of 1.26 g/100 g. The developed NIR-based method is simple, convenient, efficient and promising. It can be applied for real-time online determination of starch content in sweet potatoes after harvest to further use in food and other industry.

关键词： Near -infrared Sweet potato Starch prediction linear algorithm Online determination

来源：评论

学校读者我要写书评

暂无评论

A linear Time algorithm for Weighted k-Fair Domination Problem in Cactus Graphs

引用

Operations Research Forum 2022年第3期3卷 46页

作者： Novak, Tina Žerovnik, Janez University of Ljubljana Faculty of Mechanical Engineering Aškerčeva 6 Ljubljana 1000 Slovenia Institute of Mathematics Physics and Mechanics Jadranska 19 Ljubljana 1000 Slovenia Pipistrel Vertical Solutions d.o.o. Vipavska cesta 2 Ajdovščina 5270 Slovenia

A set D of vertices in a graph G is a k-fair dominating set if every vertex not in D is adjacent to exactly k vertices in D. The weighted k-fair domination number wfd k(G) of a vertex-weighted graph G is the minimum w... 详细信息

A set D of vertices in a graph G is a k-fair dominating set if every vertex not in D is adjacent to exactly k vertices in D. The weighted k-fair domination number wfd _k(G) of a vertex-weighted graph G is the minimum weight w(D) among all k-fair dominating sets D. In addition to the weighted k-fair domination number, some auxiliary parameters are defined. It is shown that for a cactus graph, the weighted k-fair domination number and auxiliary parameters can be calculated in linear time. © 2022, The Author(s), under exclusive licence to Springer Nature Switzerland AG.

关键词： Cactus graph DFS structure linear algorithm Weighted k-fair domination

来源：评论

学校读者我要写书评

暂无评论

An Accurate 1D Camera Calibration Based on Weighted Similar-Invariant linear algorithm 13th

An Accurate 1D Camera Calibration Based on Weighted Similar-...

引用

13th Multi-Disciplinary International Conference on Multi-Disciplinary Trends in Artificial Intelligence (MIWAI)

作者： Lin, Lixia Wu, Lijun Lai, Songlin Chen, Zhicong Lin, Peijie Wu, Zhenhui Fuzhou Univ Coll Phys & Informat Engn Fuzhou 350116 Peoples R China State Grid Fuzhou Elect Power Supply Co Fuzhou 350116 Peoples R China

ISBN: (纸本)9783030337094;9783030337087

In recent years, researchers around the world have been researching and improving the technique of 1D calibration of cameras. The previous work has been primarily focused on reducing the motion constraints of one-dimensional calibration objects, however the accuracy of the existing methods still needs to be improved when random noise is introduces. In order to improve the accuracy of the one-dimensional calibration of the camera, in this paper, we propose a new calibration method by combining a weighted similar invariant linear algorithm and an improved nonlinear optimization algorithm. Specifically, we use the weighted similar invariant linear algorithm to obtain the camera parameters as the initial calibration parameters, and then optimize the parameters by using improved nonlinear algorithm. Finally, in the case of introducing random noise, the results of computer simulations and laboratory experiments show that when the noise level reaches 2 pixels, the parameter error of this method is mostly reduced to 0.2% compared with other methods, which verifies the feasibility of our proposed method.

关键词： Camera calibration linear algorithm Nonlinear optimization 1D calibration objects

来源：评论

学校读者我要写书评

暂无评论

linear algorithm for a Cyclic Graph Transformation

引用

LOBACHEVSKII JOURNAL OF MATHEMATICS 2018年第9期39卷 1217-1227页

作者： Lyubetsky, V. A. Lyubetskaya, E. Gorbunov, K. Russian Acad Sci Kharkevich Inst Inst Informat Transmiss Problems Bolshoi Karetnyi Per 19Str 1 Moscow 127051 Russia Lomonosov Moscow State Univ Fac Mech & Math Moscow 119991 Russia

We propose a linear time and linear space algorithm that constructs a minimal (in the total cost) sequence of operations required to transform a directed graph consisting of disjoint cycles into any graph of the same type. The following operations are allowed: double-cut-and-join of vertices and insertion or deletion of a connected fragment of edges;the latter two operations have the same cost. We present a complete proof that the algorithm finds the corresponding minimum. The problem is a nontrivial particular case of the general problem of transforming a graph into another, which in turn is an instance of a hard optimization problem in graphs. In this general problem, which is known to be NP-complete, each vertex of a graph is of degree 1 or 2, edges with the same name may repeat unlimitedly, and operations belong to a well-known list including the above-mentioned operations. We describe our results for the general problem, but the proof is given for the cyclic case only.

关键词： graph cycle graph rearrangement operation cost combinatorial problem optimization in graphs linear algorithm

来源：评论

学校读者我要写书评

暂无评论

A Fast linear algorithm for Magnetic Dipole Localization Using Total Magnetic Field Gradient

引用

IEEE SENSORS JOURNAL 2018年第3期18卷 1032-1038页

作者： Fan, Liming Kang, Xiyuan Zheng, Quan Zhang, Xiaojun Liu, Xuejun Chen, Chunlei Kang, Chong Harbin Engn Univ Coll Mech & Elect Engn Harbin 150001 Heilongjiang Peoples R China Harbin Engn Univ Coll Comp Sci & Technol Harbin 150001 Heilongjiang Peoples R China Harbin Engn Univ Coll Sci Harbin 150001 Heilongjiang Peoples R China

Localization of magnetic target can be estimated through a magnetic anomaly. Generally, we need to solve the high-order nonlinear equations for estimating the position and magnetic moment of the target. Therefore, optimization algorithms are applied to calculate the solution of the nonlinear equations. In this paper, we present a fast linear algorithm for locating the target based on the total magnetic field gradient. In the algorithm, we give the closed-form formula of the static magnetic target localization. According to the properties of the vector, we can obtain a cubic equation of any 1-D position of the target. Thus, we can easily solve the cubic equation and obtain the closed-form formula of the target localization. Compared with the optimization algorithms, the proposed method provides good performance using short time and can be used to locate the target in real time. The proposed method is validated by the numerical simulation and real experimental data. The position and magnetic moment of the target are calculated rapidly. And the results show that the estimated parameters of the static target using the proposed method are very close to the true values.

关键词： Total field gradient inverse problem localization linear algorithm magnetic target

来源：评论

学校读者我要写书评

暂无评论

LAMOS: A linear algorithm to identify the origin of multiple optimal flux distributions in metabolic networks

引用

COMPUTERS & CHEMICAL ENGINEERING 2018年 117卷 372-377页

作者： Motamedian, Ehsan Naeimpoor, Fereshteh Tarbiat Modares Univ Fac Chem Engn Dept Biotechnol POB 14155-4838 Tehran Iran Iran Univ Sci & Technol Sch Chem Petr & Gas Engn Biotechnol Res Lab POB 16846-13114 Tehran Iran

In flux balance analysis, where flux distribution within a cell metabolic network is estimated by optimizing an objective function, there commonly exist multiple optimal flux distributions. Although finding all optimal solutions is possible, their interpretation is a challenge. A new four-phase algorithm (LAMOS) is therefore proposed in this work to efficiently enumerate all of these solutions based on iterative substitution of a current non-basic variable with a basic variable. These basic and non-basic variables are called key reaction pairs that their successive activity or inactivity causes alternate optimal solutions. LAMOS was implemented on E. coli metabolic models and the results proved it as a simple and fast method capable of finding the key reactions as well as reactions participating in the futile cycles. Key reactions were 1-3% of all reactions for the large-scale models and these reactions were identified using only 1% of optimal solutions. (C) 2018 Elsevier Ltd. All rights reserved.

关键词： Genome- scale metabolic network Flux balance analysis Multiple optimal solution linear algorithm Internal and futile cycles, Key reactions

来源：评论

学校读者我要写书评

暂无评论

A linear algorithm for Restructuring a Graph

引用

AUTOMATION AND REMOTE CONTROL 2018年第12期79卷 2203-2216页

作者： Gorbunov, K. Yu. Lyubetsky, V. A. Russian Acad Sci Kharkevich Inst Inst Informat Transmiss Problems Moscow Russia Lomonosov State Univ Moscow Russia

We propose an algorithm, linear in both running time and memory, that constructs a sequence of operations that transform any given directed graph with degree of any vertex at most two to any other given graph of the same type with minimal total cost. This sequence is called the shortest one. We allow four standard operations of re-gluing graphs with equal cost and two more additional operations of inserting and deleting a connected section of edges that also have equal cost. We prove that the algorithm finds a minimum with this restriction on the costs.

关键词： graph cycle chain graph transformation operation cost combinatorial problem optimization on graphs linear algorithm

来源：评论

学校读者我要写书评

暂无评论

A linear algorithm for a perfect matching in polyomino graphs

引用

THEORETICAL COMPUTER SCIENCE 2017年 675卷 82-88页

作者： Lin, Yuqing Zhang, Fuji Univ Newcastle Sch Elect Engn & Comp Sci Callaghan NSW 2308 Australia Xiamen Univ Sch Math Sci Xiamen 361005 Fujian Peoples R China

关键词： linear algorithm Polyomino graphs Perfect matching

来源：评论

学校读者我要写书评

暂无评论

A linear algorithm for the Shortest Transformation of Graphs with Different Operation Costs

引用

JOURNAL OF COMMUNICATIONS TECHNOLOGY AND ELECTRONICS 2017年第6期62卷 653-662页

作者： Gorbunov, K. Yu. Lyubetsky, V. A. Russian Acad Sci Kharkevich Inst Informat Transmiss Problems Moscow 127051 Russia

A novel time-and memory-efficient algorithm for solving the problem of finding the most economical (i.e., having the lowest overall cost) transformation of an arbitrary oriented graph representing a disjoint union of chains and cycles into another graph of the same type is proposed. The correctness of this algorithm (i.e., the fact that it always yields the minimum of the overall cost functional) and the linearity of the estimated memory and time of its operation are demonstrated.

关键词： linear algorithm oriented graph chain cycle graph transformation operation cost combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：