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

linear-time algorithm in Bayesian Image Denoising based on Gaussian Markov Random Field

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2018年第6期E101D卷 1629-1639页

作者： Yasuda, Muneki Watanabe, Junpei Kataoka, Shun Tanaka, Kazuyuki Yamagata Univ Grad Sch Sci & Engn Yonezawa Yamagata 9928510 Japan Otaru Univ Fac Commerce Otaru Hokkaido 0478571 Japan Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan

In this paper, we consider Bayesian image denoising based on a Gaussian Markov random field (GMRF) model, for which we propose an new algorithm. Our method can solve Bayesian image denoising problems, including hyperparameter estimation, in O(n)-time, where n is the number of pixels in a given image. From the perspective of the order of the computational time, this is a state-of-the-art algorithm for the present problem setting. Moreover, the results of our numerical experiments we show our method is in fact effective in practice.

关键词： Bayesian image denoising Gaussian Markov random field EM algorithm mean-field method linear-time algorithm

来源：评论

学校读者我要写书评

暂无评论

A linear-time algorithm FOR FINDING APPROXIMATE SHORTEST COMMON SUPERSTRINGS

引用

algorithmICA 1990年第3期5卷 313-323页

作者： UKKONEN, E 1. Department of Computer Science University of Helsinki Teollisuuskatu 23 SF-00510 Helsinki Finland

Approximate shortest common superstrings for a given setR of strings can be constructed by applying the greedy heuristics for finding a longest Hamiltonian path in the weighted graph that represents the pairwise overlaps between the strings inR. We develop an efficient implementation of this idea using a modified Aho-Corasick string-matching automaton. The resulting common superstring algorithm runs in timeO(n) or in timeO(n min(logm, log|Σ|)) depending on whether or not the goto transitions of the Aho-Corasick automaton can be implemented by direct indexing over the alphabet Σ. Heren is the total length of the strings inR andm is the number of such strings. The best previously known method requires timeO(n logm) orO(n logn) depending on the availability of direct indexing.

关键词： Shortest common superstring Approximation algorithm linear-time algorithm Greedy heuristics Hamiltonian path

来源：评论

学校读者我要写书评

暂无评论

A linear-time algorithm for the generation of trees

引用

algorithmICA 1997年第2期17卷 162-182页

作者： Alonso, L Remy, JL Schott, R CRIN INRIA-Lorraine Université de Nancy 1 Vandoeuvre-lès-Nancy France

We present a linear algorithm which generates randomly and with uniform probability many kinds of trees: binary trees, ternary trees, arbitrary trees, forests of p k-ary trees,.... The algorithm is based on the defini... 详细信息

关键词： coding linear-time algorithm random generation trees

来源：评论

学校读者我要写书评

暂无评论

A linear-time algorithm for finding Hamiltonian cycles in rectangular grid graphs with two rectangular holes

引用

OPTIMIZATION METHODS & SOFTWARE 2023年第3期38卷 591-625页

作者： Keshavarz-Kohjerdi, Fatemeh Bagheri, Alireza Shahed Univ Dept Comp Sci Tehran Iran Amirkabir Univ Technol Dept Comp Engn Tehran Polytech Tehran Iran Shahed Univ Persian Gulf HighwayFront Imam Khomeini Holy Shri Tehra Iran

The Hamiltonian cycle problem is one of the most important problems in graph theory that has many applications. This problem is NP-complete for general grid graphs. For solid grid graphs, there are polynomial-time algorithms. Existence of polynomial-time algorithms for grid graphs with few holes has been asked in the literature. In this paper, we give a linear-time algorithm for rectangular grid graphs with two rectangular holes. This extends the previous result for rectangular grid graphs with one rectangular hole. We first present the forbidden conditions in which there is no Hamiltonian cycle for any grid graphs, including rectangular grid graphs with rectangular holes. We then show that if these forbidden conditions do not hold, then there exists a Hamiltonian cycle. The proof is constructive, therefore, it gives an algorithm. An application of the problem is in off-line robot exploration.

关键词： Hamiltonian cycle grid graph rectangular grid graph rectangular hole linear-time algorithm off-line exploration

来源：评论

学校读者我要写书评

暂无评论

A linear-time algorithm for finding a paired 2-disjoint path cover in the cube of a connected graph

引用

DISCRETE APPLIED MATHEMATICS 2017年 218卷 98-112页

作者： Ihm, Insung Park, Jung-Heum Sogang Univ Dept Comp Sci & Engn Seoul South Korea Catholic Univ Korea Sch Comp Sci & Informat Engn Bucheon South Korea

For a connected graph G = (V (G), E(G)) and two disjoint subsets of V(G)A = (alpha(1), ..., alpha(k)} and B = {beta(1,) ..., beta(k)}, a paired (many-to-many) k-disjoint path cover of G joining A and B is a vertex-disjoint path cover (beta(1), ..., beta(k)} such that P-i is a path from alpha(i) to beta(i) for 1 <= i <= k. In the recent paper, Park and Ihm (2014) presented a necessary and sufficient condition for a paired 2-disjoint path cover joining two vertex sets to exist in the cube of a connected graph. In this paper, we propose an O vertical bar V(G)vertical bar + vertical bar E(G)vertical bar)-time algorithm that actually finds such a paired 2-disjoint path cover. In particular, we show that, in order to build a desired disjoint path cover, it is sufficient to consider only the edges of a carefully selected spanning tree of the graph and at most one additional edge not in the tree, which allows an efficient linear-time algorithm. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Disjoint path cover Cube of graph Hamiltonian path Spanning tree Unicyclic graph linear-time algorithm

来源：评论

学校读者我要写书评

暂无评论

A linear-time algorithm for clique-coloring planar graphs

引用

OPERATIONS RESEARCH LETTERS 2019年第4期47卷 241-243页

作者： Liang, Zuosong Shan, Erfang Xing, Huiyu Bai, Chunsong Qufu Normal Univ Sch Management Rizhao 276800 Peoples R China Shanghai Univ Sch Management Shanghai 200444 Peoples R China Fuyang Normal Univ Sch Math & Stat Fuyang 236041 Peoples R China

A clique of a graph G is a set of pairwise adjacent vertices of G. A clique-coloring of G is an assignment of colors to the vertices of G such that no inclusion-wise maximal clique of size at least 2 is monochromatic. Mohar and Skrekovski proved that planar graphs are 3-clique-colorable (Electr. J. Combin. 6 (1999), #R26). In this paper we present a linear time algorithm for 3-clique-coloring planar graphs by giving a new proof that planar graphs are 3-clique-colorable. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Graph Clique-coloring Planar graph linear-time algorithm

来源：评论

学校读者我要写书评

暂无评论

An almost linear-time algorithm for trapezoidation of GIS polygons

引用

FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE 2004年第7期20卷 1145-1155页

作者： Lorenzetto, GP Datta, A Univ Western Australia Sch Comp Sci & Software Engn Perth WA 6009 Australia

The decomposition of planar polygons into triangles is a well studied area of computer graphics with particular relevance to geographic information systems (GIS). Trapezoidation is often performed as a first step to triangulation. There is a complex linear-time algorithm [Discrete Comput. Geom. 6 (1991) 4851 for the decomposition of a simple polygon into triangles. However, it is extremely complicated and in practice O(n log n) algorithms are used. Our motivation in trapezoidation of large GIS polygons is the fast display of such polygons. It is much faster to display simple shapes like triangles or trapezoids on raster graphics devices, compared to complex polygons. Hence, quite often complex polygons are decomposed into triangles or trapezoids for displaying. Since triangulation is usually more difficult compared to trapezoidation, we are interested in trapezoidation of GIS polygons for faster display. We present a very simple algorithm for the trapezoidation of simple polygons without holes. Our algorithm runs in O(n) time in practice with a very small hidden constant. We have extensively tested our algorithm for polygons in a GIS database. Our algorithm is easy to implement compared to existing algorithms and runs extremely fast even for polygons with thousands of vertices. (C) 2003 Elsevier B.V. All rights reserved.

关键词： simple polygon triangulation trapezoidation raster display linear-time algorithm sweeplines

来源：评论

学校读者我要写书评

暂无评论

A linear-time algorithm to solve the Sports League Scheduling Problem (prob026 of CSPLib)

引用

DISCRETE APPLIED MATHEMATICS 2004年第1-3期143卷 252-265页

作者： Hamiez, JP Hao, JK Univ Angers LERIA F-49045 Angers 01 France Ecole Mines Ales EERIE LGI2P F-30035 Nimes 01 France

In this paper, we present a repair-based linear-time algorithm to solve a version of the Sports League Scheduling Problem (SLSP) where the number T of teams is such that (T - 1) mod 3 not equal 0. Starting with a conflicting schedule with particular properties, the algorithm removes iteratively the conflicts by exchanging matches. The properties of the initial schedule make it possible to take the optimal exchange at each iteration, leading to a linear-time algorithm. This algorithm can find thus valid schedules for several thousands of teams in less than 1 min. It is still an open question whether the SLSP can be solved efficiently when (T - 1) mod 3 = 0. (C) 2004 Elsevier B.V. All rights reserved.

关键词： Sports League Scheduling linear-time algorithm repair techniques

来源：评论

学校读者我要写书评

暂无评论

A linear-time algorithm for reconstructing zero-recombinant haplotype configuration on pedigrees without mating loops

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2010年第2期19卷 217-240页

作者： Liu, Lan Jiang, Tao Univ Calif Riverside Dept Comp Sci & Engn Riverside CA 92507 USA Google Inc Mountain View CA 94043 USA

With the launch of the international HapMap project, the haplotype inference problem has attracted a great deal of attention in the computational biology community recently. In this paper, we study the question of how to efficiently infer haplotypes from genotypes of individuals related by a pedigree without mating loops, assuming that the hereditary process was free of mutations (i.e. the Mendelian law of inheritance) and recombinants. We model the haplotype inference problem as a system of linear equations as in (Xiao et al. in Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete algorithms (SODA'07), pp. 655-664, 2007) and present an (optimal) linear-time (i.e. O(mn) time) algorithm to generate a particular solution to the haplotype inference problem, where m is the number of loci (or markers) in a genotype and n is the number of individuals in the pedigree. Moreover, the algorithm also provides a general solution in O(mn (2)) time, which is optimal because the descriptive size of a general solution could be as large as I similar to(mn (2)). The key ingredients of our construction are (i) a fast consistency checking procedure for the system of linear equations introduced in (Xiao et al. 2007) based on a careful investigation of the relationship between the equations (ii) a novel linear-time method for solving linear equations without invoking the Gaussian elimination method. Although such a fast method for solving equations is not known for general systems of linear equations, we take advantage of the underlying loop-free pedigree graph and some special properties of the linear equations.

关键词： Haplotype inference Pedigree analysis Mating loop Tree-pedigree linear-time algorithm System of linear equation General solution

来源：评论

学校读者我要写书评

暂无评论

A linear-time algorithm for connected r-domination and Steiner tree on distance-hereditary graphs

引用

NETWORKS 1998年第3期31卷 177-182页

作者： Brandstadt, A Dragan, FF Univ Rostock Fachbereich Informat Lehrstuhl Theoret Informat D-18051 Rostock Germany

A distance-hereditary graph is a connected graph in which every induced path is isometric, i.e., the distance of any two vertices in an induced path equals their distance in the graph. We present a linear time labeling algorithm for the minimum cardinality connected r-dominating set and Steiner tree problems on distance-hereditary graphs. (C) 1998 John Wiley & Sons, Inc.

关键词： connected domination Steiner tree distance-hereditary graph linear-time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：