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

Bounded workspace garbage collection in an address-order preserving list processing environment

引用

Information Processing Letters 1974年第1期3卷 29-32页

作者： Fisher, David A. Science and Technology Division Institute for Defense Analyses Arlington VA 22202 United States

来源：评论

学校读者我要写书评

暂无评论

Efficient Edge Domination on Hole-Free Graphs in Polynomial time

Efficient Edge Domination on Hole-Free Graphs in Polynomial ...

引用

9th Latin American Symposium on Theoretical Informatics (LATIN 2010)

作者： Brandstaedt, Andreas Hundt, Christian Nevries, Ragnar Univ Rostock Inst Informat D-18051 Rostock Germany

ISBN: (纸本)9783642121999

This paper deals with the Efficient Edge Domination Problem (EED, for short), also known as Dominating Induced Matching Problem. For an undirected graph G = (V, E) FED asks for an induced matching M subset of E that simultaneously dominates all edges of G. Thus, the distance between edges of M is at least two and every edge in E is adjacent to an edge of M. EED is related to parallel resource allocation problems, encoding theory and network routing. The problem is NP-complete even for restricted classes like planar bipartite and bipartite graphs with maximum degree three. However, the complexity has been open for chordal bipartite graphs. This paper shows that EED can be solved in polynomial time on hole-free graphs. Moreover, it provides even linear time for chordal bipartite graphs. Finally, we strengthen the NP-completeness result to planar bipartite graphs of maximum degree three.

关键词： efficient edge domination dominating induced matching chordal bipartite graphs weakly chordal graphs hole-free graphs linear time algorithm polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

On the implementation and refinement of outerplanar graph algorithms.

On the implementation and refinement of outerplanar graph al...

引用

作者： Tao Deng University of Windsor

学位级别：硕士

An outerplanar graph is a graph that can be embedded on the plane such that all the vertices lie on the exterior face and no two edges intersect except possibly at a common end-vertex. Five sequential algorithms had been proposed for rec ognizing outerplanar graph in the literature and all run in linear time and space. Although among them, the algorithms of Mitchell, Wiegers, and Tsin and Lin are obviously superior, no efforts had been made in comparing their performances during run-time. In this thesis, the aforementioned three algorithms are implemented and their performances are compared using a large number of randomly generated graphs. Furthermore, the algorithms of Mitchell and Wiegers are modified so that an out- erpalnar embedding is generated if the input graph is outerplanar. Correctness proofs of the modification are presented. It is also shown that the complexity of the modified algorithms remain linear in both time and space.

关键词： Graph algorithms outerplanar graph outerplanar embedding linear time algorithm performance evaluation

来源：评论

学校读者我要写书评

暂无评论

algorithms and complexity for geodetic sets on partial grids

引用

THEORETICAL COMPUTER SCIENCE 2023年 979卷

作者： Chakraborty, Dibyayan Gahlawat, Harmender Roy, Bodhayan Univ Leeds Sch Comp Leeds England Ben Gurion Univ Negev IL-84105 Beer Sheva Israel Indian Inst Technol Kharagpur India

A set S of vertices of a graph G is a geodetic set if every vertex of G lies in a shortest path between some pair of vertices of S. The MINIMUM GEODETIC SET (MGS) problem is to find a geodetic set with minimum cardinality of a given graph. A grid embedding of a graph is a set of points in two dimensions with integer coordinates such that each point in the set represents a vertex of the graph and, for each edge, the points corresponding to its endpoints are at Euclidean distance 1. A graph is a partial grid if it has a grid embedding. In this paper, we first prove that MINIMUM GEODETIC SET remains NP-hard even for subcubic partial grids of arbitrary girth. This jointly strengthens three existing hardness results: for bipartite graphs (Dourado et al. 2010 [11]), subcubic graphs (Bueno et al. 2018 [4]), and planar graphs (Chakraborty et al. 2020 [6]). The area of an internal face is the number of integer points lying on the boundary or interior of the face. A graph is a solid grid if it has a grid embedding such that all interior faces have area exactly four. To complement the above hardness result, we design a linear-time algorithm for MINIMUM GEODETIC SET on solid grids, improving on a 3-approximation algorithm by Chakraborty et al. (2020) [6].Our results hold for EDGE GEODETIC SET as well. A set S of vertices of a graph G is a geodetic set if every edge of G lies in a shortest path between some pair of vertices of S. The MINIMUM EDGE GEODETIC SET (MEGS) problem is to find an edge geodetic set with minimum cardinality of a given graph. As corollaries, we obtain that MEGS remains NP-hard on partial grids and is linear-time solvable on solid grids.

关键词： Geodetic set Partial grids Solid grids NP-hardness linear time algorithm

来源：评论

学校读者我要写书评

暂无评论

algorithms for locating extremely conserved elements in multiple sequence alignments

引用

BMC BIOINFORMATICS 2009年第1期10卷 1-8页

作者： Tseng, Huei-Hun E. Tompa, Martin Univ Washington Dept Comp Sci & Engn Seattle WA 98195 USA Univ Washington Dept Genome Sci Seattle WA 98195 USA

Background: In 2004, Bejerano et al. announced the startling discovery of hundreds of "ultraconserved elements", long genomic sequences perfectly conserved across human, mouse, and rat. Their announcement stimulated a flurry of subsequent research. Results: We generalize the notion of ultraconserved element in a natural way from extraordinary human-rodent conservation to extraordinary conservation over an arbitrary set of species. We call these "Extremely Conserved Elements". There is a linear time algorithm to find all such Extremely Conserved Elements in any multiple sequence alignment, provided that the conservation is required to be across all the aligned species. For the general case of conservation across an arbitrary subset of the aligned species, we show that the question of whether there exists an Extremely Conserved Element is NP-complete. We illustrate the linear time algorithm by cataloguing all 177 Extremely Conserved Elements in the currently available 44-vertebrate whole-genome alignment, and point out some of the characteristics of these elements. Conclusions: The NP-completeness in the case of conservation across an arbitrary subset of the aligned species implies that it is unlikely an efficient algorithm exists for this general case. Despite this fact, for the interesting case of conservation across all or most of the aligned species, our algorithm is efficient enough to be practical. The 177 Extremely Conserved Elements that we catalog demonstrate many of the characteristics of the original ultraconserved elements of Bejerano et al.

关键词： Fugu linear time algorithm Alignment Column Alignment Block Extreme Conservation

来源：评论

学校读者我要写书评

暂无评论

Complexity and algorithms for injective edge coloring of graphs

引用

THEORETICAL COMPUTER SCIENCE 2023年第1期968卷

作者： Priyamvada, B. S. Panda, B. S. Indian Inst Technol Delhi Dept Math New Delhi 110016 India

An injective k-edge-coloring of a graph G = (V, E) is an assignment & omega;: E & RARR;{1, 2, ... , k} of colors to the edges of G such that any two edges e and f receive distinct colors if there exists an edge g = xy different from e and f such that e is incident on x and f is incident on y. The minimum value of k for which G admits an injective k-edgecoloring is called the injective chromatic index of G and is denoted by & chi;i (G). Given a graph G and a positive integer k, the INJECTIVE EDGE COLORING PROBLEM is to decide whether G admits an injective k-edge-coloring. It is known that INJECTIVE EDGE COLORING PROBLEM is NP-complete for general graphs. In this paper, we strengthen this result by proving that INJECTIVE EDGE COLORING PROBLEM is NP-complete for bipartite graphs by proving that this problem remains NP-complete for perfect elimination bipartite graphs and star-convex bipartite graphs, which are proper subclasses of bipartite graphs. On the positive side, we propose a linear time algorithm for computing the injective chromatic index of chain graphs, which is a proper subclass of both perfect elimination bipartite graphs and starconvex bipartite graphs.

关键词： Injective edge coloring NP-complete linear time algorithm

来源：评论

学校读者我要写书评

暂无评论

Reconstructing genome mixtures from partial adjacencies

引用

BMC BIOINFORMATICS 2012年第19-sup期13卷 S9-S9页

作者： Mahmoody, Ahmad Kahn, Crystal L. Raphael, Benjamin J. Brown Univ Dept Comp Sci Providence RI 02912 USA

Many cancer genome sequencing efforts are underway with the goal of identifying the somatic mutations that drive cancer progression. A major difficulty in these studies is that tumors are typically heterogeneous, with individual cells in a tumor having different complements of somatic mutations. However, nearly all DNA sequencing technologies sequence DNA from multiple cells, thus resulting in measurement of mutations from a mixture of genomes. Genome rearrangements are a major class of somatic mutations in many tumors, and the novel adjacencies (i.e. breakpoints) resulting from these rearrangements are readily detected from DNA sequencing reads. However, the assignment of each rearrangement, or adjacency, to an individual cancer genome in the mixture is not known. Moreover, the quantity of DNA sequence reads may be insufficient to measure all rearrangements in all genomes in the tumor. Motivated by this application, we formulate the k-minimum completion problem (k-MCP). In this problem, we aim to reconstruct k genomes derived from a single reference genome, given partial information about the adjacencies present in the mixture of these genomes. We show that the 1-MCP is solvable in linear time in the cases where: (i) the measured, incomplete genome has a single circular or linear chromosome;(ii) there are no restrictions on the chromosomal content of the measured, incomplete genome. We also show that the k-MCP problem, for k >= 3 in general, and the 2-MCP problem with the double-cut-and-join (DCJ) distance are NP-complete, when there are no restriction on the chromosomal structure of the measured, incomplete genome. These results lay the foundation for future algorithmic studies of the k-MCP and the application of these algorithms to real cancer sequencing data.

关键词： Reference Genome linear time algorithm Partial Genome Blue Edge Mixture Tree

来源：评论

学校读者我要写书评

暂无评论

Computing evolutionary distinctiveness indices in large scale analysis

引用

algorithmS FOR MOLECULAR BIOLOGY 2012年第1期7卷 6-6页

作者： Martyn, Iain Kuhn, Tyler S. Mooers, Arne O. Moulton, Vincent Spillner, Andreas Simon Fraser Univ IRMACS & BioSci Burnaby BC V5A 1S6 Canada Penn State Univ Dept Biol Mueller Lab 208 University Pk PA 16802 USA Univ E Anglia Sch Comp Sci Norwich NR4 7TJ Norfolk England Univ Greifswald Dept Math & Comp Sci D-17487 Greifswald Germany

We present optimal linear time algorithms for computing the Shapley values and 'heightened evolutionary distinctiveness' (HED) scores for the set of taxa in a phylogenetic tree. We demonstrate the efficiency of these new algorithms by applying them to a set of 10,000 reasonable 5139-species mammal trees. This is the first time these indices have been computed on such a large taxon and we contrast our finding with an ad-hoc index for mammals, fair proportion (FP), used by the Zoological Society of London's EDGE programme. Our empirical results follow expectations. In particular, the Shapley values are very strongly correlated with the FP scores, but provide a higher weight to the few monotremes that comprise the sister to all other mammals. We also find that the HED score, which measures a species' unique contribution to future subsets as function of the probability that close relatives will go extinct, is very sensitive to the estimated probabilities. When they are low, HED scores are less than FP scores, and approach the simple measure of a species' age. Deviations (like the Solendon genus of the West Indies) occur when sister species are both at high risk of extinction and their clade roots deep in the tree. Conversely, when endangered species have higher probabilities of being lost, HED scores can be greater than FP scores and species like the African elephant Loxondonta africana, the two solendons and the thumbless bat Furipterus horrens can move up the rankings. We suggest that conservation attention be applied to such species that carry genetic responsibility for imperiled close relatives. We also briefly discuss extensions of Shapley values and HED scores that are possible with the algorithms presented here.

关键词： Phylogenetic Diversity Fair Proportion linear time algorithm African Elephant Unrooted Tree

来源：评论

学校读者我要写书评

暂无评论

Superbubbles revisited

引用

algorithmS FOR MOLECULAR BIOLOGY 2018年第1期13卷 16-16页

作者： Gaertner, Fabian Mueller, Lydia Stadler, Peter F. Univ Leipzig Competence Ctr Scalable Data Serv & Solut Dresden Augustuspl 12 D-04107 Leipzig Germany Univ Leipzig Bioinformat Grp Dept Comp Sci Hartelstr 16 D-04107 Leipzig Germany Univ Leipzig Interdisciplinary Ctr Bioinformat Hartelstr 16-18 D-04107 Leipzig Germany Univ Leipzig Dept Comp Sci Nat Language Proc Grp Augustuspl 12 D-04107 Leipzig Germany Max Planck Inst Math Sci Inselstr 22 D-04103 Leipzig Germany Fraunhofer Inst Cell Therapy & Immunol Perlickstr 1 D-04103 Leipzig Germany Univ Vienna Dept Theoret Chem Wahringer Str 17 A-1090 Vienna Austria Ctr Noncoding RNA Technol & Hlth Gronegardsvej 3 DK-1870 Frederiksberg C Denmark Santa Fe Inst 1399 Hyde Pk Rd Santa Fe NM 87501 USA

Background: Superbubbles are distinctive subgraphs in direct graphs that play an important role in assembly algorithms for high- throughput sequencing ( HTS) data. Their practical importance derives from the fact they are connected to their host graph by a single entrance and a single exit vertex, thus allowing them to be handled independently. Efficient algorithms for the enumeration of superbubbles are therefore of important for the processing of HTS data. Superbubbles can be identified within the strongly connected components of the input digraph after transforming them into directed acyclic graphs. The algorithm by Sung et al. ( IEEE ACM Trans Comput Biol Bioinform 12: 770- 777, 2015) achieves this task in O( m log( m))- time. The extraction of superbubbles from the transformed components was later improved to by Brankovic et al. ( Theor Comput Sci 609: 374- 383, 2016) resulting in an overall O( m + n)- time algorithm. Results: A re- analysis of the mathematical structure of superbubbles showed that the construction of auxiliary DAGs from the strongly connected components in the work of Sung et al. missed some details that can lead to the reporting of false positive superbubbles. We propose an alternative, even simpler auxiliary graph that solved the problem and retains the linear running time for general digraph. Furthermore, we describe a simpler, space- efficient O( m + n) - time algorithm for detecting superbubbles in DAGs that uses only simple data structures. Implementation: We present a reference implementation of the algorithm that accepts many commonly used formats for the input graph and provides convenient access to the improved algorithm. https :// githu b. com/ Fabia nexe/ Super bubble

关键词： Superbubble de Bruijn graph Genome assembly linear time algorithm

来源：评论

学校读者我要写书评

暂无评论

Direct Superbubble Detection

引用

algorithmS 2019年第4期12卷 81-81页

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

Superbubbles are a class of induced subgraphs in digraphs that play an essential role in assembly algorithms for high-throughput sequencing data. They are connected with the remainder of the host digraph by a single entrance and a single exit vertex. linear-time algorithms for the enumeration superbubbles recently have become available. Current approaches require the decomposition of the input digraph into strongly-connected components, which are then analyzed separately. In principle, a single depth-first search could be used, provided one can guarantee that the root of the depth-first search (DFS)-tree is not itself located in the interior or the exit point of a superbubble. Here, we describe a linear-time algorithm to determine suitable roots for a DFS-forest that is guaranteed to identify the superbubbles in a digraph correctly. In addition to the advantages of a more straightforward implementation, we observe a nearly three-fold gain in performance on real-world datasets. We present a reference implementation of the new algorithm that accepts many commonly-used input formats for digraphs. It is available as open source from github.

关键词： superbubble depth-first search cycles linear time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：