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

Secure total domination in chain graphs and cographs

AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS 2020年第3期17卷 826-832页

作者： Jha, Anupriya Indian Inst Technol ISM Dept Math & Comp Dhanbad Bihar India

Let G = (V,E) be a graph without isolated vertices. A subset D of vertices of G is called a total dominating set of G if for every u is an element of V, there exists a vertex v is an element of D such that uv is an element of E. A total dominating set D of a graph G is called a secure total dominating set of G if for every u is an element of V\D, there exists a vertex v is an element of D such that uv is an element of E and (D\{v}){u} is a total dominating set of G. The secure total domination number of G, denoted by gamma st(G), is the minimum cardinality of a secure total dominating set of G. Given a graph G, the secure total domination problem is to find a secure total dominating set of G with minimum cardinality. In this paper, we first show that the secure total domination problem is linear time solvable on graphs of bounded clique-width. We then propose linear time algorithms for computing the secure total domination number of chain graphs and cographs.

关键词： Total domination secure total domination chain graphs cographs linear time algorithm

来源：评论

学校读者我要写书评

暂无评论

THE UNIQUELY SOLVABLE BIPARTITE MATCHING PROBLEM

引用

OPERATIONS RESEARCH LETTERS 1991年第4期10卷 221-224页

作者： CECHLAROVA, K Department of Geometry and Algebra P.J. Šafárik's University Jesenná 5 041 54 Košice Czechoslovakia

The bipartite cardinality matching problem can be solved by a well-known algorithm with complexity O(\E\.\V\1/2). We give a characterization of the bipartite graphs with a unique maximum matching and an O(\E\) algorit... 详细信息

关键词： BIPARTITE GRAPH MATCHING linear time algorithm

来源：评论

学校读者我要写书评

暂无评论

Efficient scan mask techniques for connected components labeling algorithm

引用

EURASIP JOURNAL ON IMAGE AND VIDEO PROCESSING 2011年第1期2011卷 1-20页

作者： Sutheebanjard, Phaisarn Premchaiswadi, Wichian Siam Univ Grad Sch Informat Technol Bangkok 10160 Thailand

Block-based connected components labeling is by far the fastest algorithm to label the connected components in 2D binary images, especially when the image size is quite large. This algorithm produces a decision tree that contains 211 leaf nodes with 14 levels for the depth of a tree and an average depth of 1.5923. This article attempts to provide a faster method for connected components labeling. We propose two new scan masks for connected components labeling, namely, the pixel-based scan mask and the block-based scan mask. In the final stage, the block-based scan mask is transformed to a near-optimal decision tree. We conducted comparative experiments using different sources of images for examining the performance of the proposed method against the existing methods. We also performed an average tree depth analysis and tree balance analysis to consolidate the performance improvement over the existing methods. Most significantly, the proposed method produces a decision tree containing 86 leaf nodes with 12 levels for the depth of a tree and an average depth of 1.4593, resulting in faster execution time, especially when the foreground density is equal to or greater than the background density of the images.

关键词： connected components image processing labeling algorithm linear time algorithm pattern recognition

来源：评论

学校读者我要写书评

暂无评论

linear-time protein 3-D structure searching with insertions and deletions

引用

algorithmS FOR MOLECULAR BIOLOGY 2010年第1期5卷 7-7页

作者： Shibuya, Tetsuo Jansson, Jesper Sadakane, Kunihiko Univ Tokyo Human Genome Ctr Inst Med Sci Minato Ku Tokyo 1088639 Japan Ochanomizu Univ Bunkyo Ku Tokyo 1128610 Japan Natl Inst Informat Chiyoda Ku Tokyo 1018430 Japan

Background: Two biomolecular 3-D structures are said to be similar if the RMSD (root mean square deviation) between the two molecules' sequences of 3-D coordinates is less than or equal to some given constant bound. Tools for searching for similar structures in biomolecular 3-D structure databases are becoming increasingly important in the structural biology of the post-genomic era. Results: We consider an important, fundamental problem of reporting all substructures in a 3-D structure database of chain molecules (such as proteins) which are similar to a given query 3-D structure, with consideration of indels (i.e., insertions and deletions). This problem has been believed to be very difficult but its exact computational complexity has not been known. In this paper, we first prove that the problem in unbounded dimensions is NP hard. We then propose a new algorithm that dramatically improves the average-case time complexity of the problem in 3-D in case the number of indels k is bounded by a constant. Our algorithm solves the above problem for a query of size m and a database of size N in average-case O(N) time, whereas the time complexity of the previously best algorithm was O(Nm(k+1)). Conclusions: Our results show that although the problem of searching for similar structures in a database based on the RMSD measure with indels is NP-hard in the case of unbounded dimensions, it can be solved in 3-D by a simple average-case linear time algorithm when the number of indels is bounded by a constant.

关键词： Text Structure Chain Molecule linear time algorithm Textual String Preliminary Section

来源：评论

学校读者我要写书评

暂无评论

The minimum k-way cut of bounded size is fixed-parameter tractable

The minimum <i>k</i>-way cut of bounded size is fixed-parame...

引用

52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS)

作者： Kawarabayashi, Ken-ichi Thorup, Mikkel Res Org Informat & Syst Natl Inst Informat Chiyoda Ku 2-1-2 Hitotsubashi Tokyo 1018430 Japan AT&T Labs Res Florham Pk NJ 07932 USA

ISBN: (纸本)9780769545714

We consider the minimum k-way cut problem for unweighted undirected graphs with a size bound s on the number of cut edges allowed. Thus we seek to remove as few edges as possible so as to split a graph into k components, or report that this requires cutting more than s edges. We show that this problem is fixed-parameter tractable (FPT) with the standard parameterization in terms of the solution sizes. More precisely, for s=O(1), we present a quadratic time algorithm. Moreover, we present a much easier linear time algorithm for planar graphs and bounded genus graphs. Our tractability result stands in contrast to known W[1] hardness of related problems. Without the size bound, Downey et al. [2003] proved that the minimum k-way cut problem is W[1] hard with parameter k, and this is even for simple unweighted graphs. Downey et al. asked about the status for planar graphs. We get linear time with fixed parameter k for simple planar graphs since the minimum k-way cut of a planar graph is of size at most 6k. More generally, we get FPT with parameter k for any graph class with bounded average degree. A simple reduction shows that vertex cuts are at least as hard as edge cuts, so the minimum k-way vertex cut is also W[1] hard with parameter k. Marx [2004] proved that finding a minimum k-way vertex cut of size s is also W[1] hard with parameters. Marx asked about the FPT status with edge cuts, which we prove tractable here. We are not aware of any other cut problem where the vertex version is W[1] hard but the edge version is FPT, e.g., Marx [2004] proved that the k terminal cut problem is FPT parameterized by the cut size, both for edge and vertex cuts.

关键词： $k$-way-cut Approximation algorithms Approximation methods FPT Helium Kernel Minimization Polynomials Terminology bounded genus graphs bounded genus graphs edge version fixed parameter tractability graph theory linear time algorithm minimum k-way cut plan

来源：评论

学校读者我要写书评

暂无评论

Superbubbles as an empirical characteristic of directed networks

引用

NETWORK SCIENCE 2021年第1期9卷 49-58页

作者： Gaertner, Fabian Kuehnl, Felix Seemann, Carsten R. Zu Siederdissen, Christian Hoener Stadler, Peter F. Univ Leipzig Competence Ctr Scalable Data Serv & Solut Dresden Augustuspl 12 D-04107 Leipzig Germany Univ Leipzig Dept Comp Sci Bioinformat Grp Hartelstr 16-18 D-04107 Leipzig Germany Univ Leipzig Interdisciplinary Ctr Bioinformat Hartelstr 16-18 D-04107 Leipzig Germany Max Planck Inst Math Sci Inselstr 22 D-04103 Leipzig Germany Univ Leipzig German Ctr Integrat Biodivers Res iDiv Halle Jena Hartelstr 16-18 D-04107 Leipzig Germany Univ Leipzig Leipzig Res Ctr Civilizat Dis Hartelstr 16-18 D-04107 Leipzig Germany Univ Vienna Inst Theoret Chem Wahringerstr 17 A-1090 Vienna Austria Univ Nacl Colombia Fac Ciencias Sede Bogota Bogota Colombia Santa Fe Inst 1399 Hyde Pk Rd Santa Fe NM 87501 USA

Superbubbles are acyclic induced subgraphs of a digraph with single entrance and exit that naturally arise in the context of genome assembly and the analysis of genome alignments in computational biology. These structures can be computed in linear time and are confined to non-symmetric digraphs. We demonstrate empirically that graph parameters derived from superbubbles provide a convenient means of distinguishing different classes of real-world graphical models, while being largely unrelated to simple, commonly used parameters.

关键词： digraph graph descriptor bubbles linear time algorithm

来源：评论

学校读者我要写书评

暂无评论

Bipartite Grid Partitioning of a Random Geometric Graph 13

Bipartite Grid Partitioning of a Random Geometric Graph

引用

13th IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS)

作者： Chen, Zizhen Matula, David W. Southern Methodist Univ Dept Comp Sci & Engn Dallas TX 75275 USA

ISBN: (纸本)9781538639917

We investigate the problem of efficient computation of a partition of a Random Geometric Graph (RGG) into a limited number of densely packed bipartite grid sub graphs. The study focuses on the collection of subgraphs each individually having similar size and structure and the union employing most (e.g. over 85%) of the vertices. The residual vertices we seek to minimize are attributed to the inherent variations in densities of the randomly placed vertices and to any shortcomings of our greedy algorithms. RGG's have been extensively employed in recent times to model the deployment of numerous instances of Wireless Sensor Networks (WSN's) Pl. The properties investigated in our selected bipartite grid backbones are those deemed most relevant for applications to the foundations of this widely growing field. Distributed algorithms are primarily used to determine backbones. Our results review what backbone grid partitions exist in the data. This provides a metric to measure the effectiveness of any distributed algorithm against an existing optimal result. The visual display of selected backbone grids suggests local algorithm design strategies. Furthermore, these partitions must be efficiently computable for highly scalable computation, e.g. WSN's with 100's of thousands of vertices and millions of edges in the resulting RGG. We consider distributions over a segment of the plane and over the surface of the sphere to model sensor distributions both in limited planar regions, all around the globe or on distant planets.

关键词： Random Geometric Graph Wireless Sensor Network Bipartite Subgraph Grid Partitioning linear time algorithm

来源：评论

学校读者我要写书评

暂无评论

On Computing the Jaro Similarity Between Two Strings 19th

On Computing the Jaro Similarity Between Two Strings

引用

19th International Symposium on Bioinformatics Research and Applications

作者： Basak, Joyanta Soliman, Ahmed Deo, Nachiket Haase, Kenneth Mathur, Anup Park, Krista Steorts, Rebecca Weinberg, Daniel Sahni, Sartaj Rajasekaran, Sanguthevar Univ Connecticut Dept CSE Storrs CT 06268 USA US Bur Census 4600 Silver Hill Rd Hillcrest Heights MD 20746 USA Duke Univ Dept Stat Sci Durham NC 27708 USA Duke Univ Dept Comp Sci Durham NC 27708 USA Duke Univ Dept Biostat & Bioinformat Durham NC 27708 USA Duke Univ Dept Social Sci & Rhode Informat Initiat Durham NC 27708 USA Univ Florida Dept CISE Gainesville FL USA

ISBN: (纸本)9789819970735;9789819970742

Jaro similarity is widely used in computing the similarity (or distance) between two strings of characters. For example, record linkage is an application of great interest in many domains for which Jaro similarity is popularly employed. Existing algorithms for computing the Jaro similarity between two given strings take quadratic time in the worst case. In this paper, we present an algorithm for Jaro similarity computation that takes only linear time. We also present experimental results that reveal that our algorithm outperforms existing algorithms.

关键词： String similarity Jaro similarity linear time algorithm Record linkage

来源：评论

学校读者我要写书评

暂无评论

PERFORMANCE RESULTS OF THE SIMPLEX algorithm FOR A SET OF REAL-WORLD linear-PROGRAMMING MODELS

引用

COMMUNICATIONS OF THE ACM 1982年第3期25卷 207-213页

作者： MCCALL, EH UNIV MINNESOTA MINNEAPOLISMN 55455

This paper provides performance results using the SPERRY UNIVAC 1100 Series linear programming product FMPS to solve a set of 16 real-world linear programming problems. As such, this paper provides a data point for the actual performance of a commercial simplex algorithm on real-world linear programming problems and shows that the simplex algorithm is a linear time algorithm in actual performance. Correlations and performance relationships not previously available are also provided. [ABSTRACT FROM AUTHOR]

关键词： computational complexity large scale linear time algorithm polynomial time algorithm simplex algorithm

来源：评论

学校读者我要写书评

暂无评论

Planning for millions of NPCs in Real-time

Planning for millions of NPCs in Real-Time

引用

IEEE Symposium Series on Computational Intelligence (IEEE SSCI)

作者： Guillaume, Prevost Stephane, Cardon Eric, Jacopin Tristan, Cazenave Christophe, Guettier CReC St Cyr AMSCC F-56380 Guer France Univ Paris Dauphine PSL LAMSADE F-75775 Paris France Safran Safran Elect & Def F-35300 Fougeres France

ISBN: (纸本)9781665487689

We address the problem of scaling the generation of plans in real-time to control the behaviors of several millions of Non-Player Characters (NPCs) in video-games and virtual worlds. Search-based action planning, introduced in the game F.E.A.R. in 2005, has an exponential time complexity managing at most several tens of NPCs per frame. A close study of the plans generated in first-person shooters shows that: (1) states are vectors of enumerated values, (2) both initial and final states can be totally defined, (3) actions are both post-unique and unary, (4) plans are totally ordered, and (5) actions occur only once in plans. (1) to (5) satisfy the Simplified Action Structure (SAS) linear time planning framework SAS-PUT1. We strengthen previous claims on this framework saying that the associated linear time algorithm P is capable of managing several millions of NPCs per frame by testing it on three new realistic benchmarks that are based on commercial video games.

关键词： Artificial Intelligence Action Planning SAS Planning Real-time Post-unique Unary linear time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：