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

18th International Conference and Workshops on algorithms and Computation (WALCOM)

作者： Da Lozzo, Giordano Di Battista, Giuseppe Frati, Fabrizio Grosso, Fabrizio Patrignani, Maurizio Roma Tre Univ Rome Italy

ISBN: (纸本)9789819705658;9789819705665

We propose efficient algorithms for enumerating the celebrated combinatorial structures of maximal planar graphs, called canonical orderings and Schnyder woods, and the related classical graph drawings by de Fraysseix, Pach, and Pollack [Combinatorica, 1990] and by Schnyder [SODA, 1990], called canonical drawings and Schnyder drawings, respectively. To this aim (i) we devise an algorithm for enumerating special e-bipolar orientations of maximal planar graphs, called canonical orientations;(ii) we establish bijections between canonical orientations and canonical drawings, and between canonical orientations and Schnyder drawings;and (iii) we exploit the known correspondence between canonical orientations and canonical orderings, and the known bijection between canonical orientations and Schnyder woods. All our enumeration algorithms have O(n) setup time, space usage, and delay between any two consecutively listed outputs, for an n-vertex maximal planar graph.

关键词： enumeration algorithms Planar graphs Canonical orderings Schnyder woods Worst-case delay

来源：评论

学校读者我要写书评

暂无评论

Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked enumeration 21

Probabilistic Databases under Updates: Boolean Query Evaluat...

引用

40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS)

作者： Berkholz, Christoph Merz, Maximilian Humboldt Univ Inst Informat Berlin Germany

ISBN: (纸本)9781450383813

We consider tuple-independent probabilistic databases in a dynamic setting, where tuples can be inserted or deleted. In this context we are interested in efficient data structures for maintaining the query result of Boolean as well as non-Boolean queries. For Boolean queries, we show how the known lifted inference rules can be made dynamic, so that they support single-tuple updates with only a constant number of arithmetic operations. As a consequence, we obtain that the probability of every safe UCQ can be maintained with constant update time. For non-Boolean queries, our task is to enumerate all result tuples ranked by their probability. We develop lifted inference rules for non-Boolean queries, and, based on these rules, provide a dynamic data structure that allows both log-time updates and ranked enumeration with logarithmic delay. As an application, we identify a fragment of non-repeating conjunctive queries that supports log-time updates as well as log-delay ranked enumeration. This characterisation is tight under the OMv-conjecture.

关键词： enumeration algorithms probabilistic databases query evaluation under updates

来源：评论

学校读者我要写书评

暂无评论

enumeration and Updates for Conjunctive Linear Algebra Queries Through Expressibility 27

Enumeration and Updates for Conjunctive Linear Algebra Queri...

引用

27th International Conference on Database Theory (ICDT)

作者： Serrano, Thomas Munoz Riveros, Cristian Vansummeren, Stijn UHasselt Data Sci Inst Diepenbeek Belgium Pontificia Univ Catolica Chile Santiago Chile Millennium Inst Fdn Res Data Santiago Chile

ISBN: (纸本)9783959773126

Due to the importance of linear algebra and matrix operations in data analytics, there is significant interest in using relational query optimization and processing techniques for evaluating (sparse) linear programs. In particular, in recent years close connections have been established between linear algebra programs and relational algebra that allow transferring optimization techniques of the latter to the former. In this paper, we ask ourselves which linear algebra programs in MATLANG correspond to the free-connex and q-hierarchical fragments of conjunctive first-order logic. Both fragments have desirable query processing properties: free-connex conjunctive queries support constant-delay enumeration after a linear-time preprocessing phase, and q-hierarchical conjunctive queries further allow constant-time updates. By characterizing the corresponding fragments of MATLANG, we hence identify the fragments of linear algebra programs that one can evaluate with constant-delay enumeration after linear-time preprocessing and with constant-time updates. To derive our results, we improve and generalize previous correspondences between MATLANG and relational algebra evaluated over semiring-annotated relations. In addition, we identify properties on semirings that allow to generalize the complexity bounds for free-connex and q-hierarchical conjunctive queries from Boolean annotations to general semirings.

关键词： Query evaluation conjunctive queries linear algebra enumeration algorithms

来源：评论

学校读者我要写书评

暂无评论

Sublinear-space bounded-delay enumeration for massive network analytics: Maximal cliques 43

Sublinear-space bounded-delay enumeration for massive networ...

引用

43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016

作者： Conte, Alessio Grossi, Roberto Marino, Andrea Versari, Luca Dipartimento di Informatica Università di Pisa Pisa Italy Scuola Normale Superiore Pisa Italy

ISBN: (纸本)9783959770132

Due to the sheer size of real-world networks, delay and space become quite relevant measures for the cost of enumeration in network analytics. This paper presents efficient algorithms for listing maximum cliques in networks, providing the first sublinear-space bounds with guaranteed delay per enumerated clique, thus comparing favorably with the known literature. © Alessio Conte, Roberto Grossi, Andrea Marino, and Luca Versari.

关键词： enumeration algorithms Maximal cliques Network mining and analytics Reverse search Space efficiency

来源：评论

学校读者我要写书评

暂无评论

An output sensitive algorithm for maximal clique enumeration in sparse graphs 12

An output sensitive algorithm for maximal clique enumeration...

引用

12th International Symposium on Parameterized and Exact Computation, IPEC 2017

作者： Manoussakis, George LRI-CNRS Université Paris Sud Université Paris Saclay France

ISBN: (纸本)9783959770514

The degeneracy of a graph G is the smallest integer k such that every subgraph of G contains a vertex of degree at most k. Given an n-order k-degenerate graph G, we present an algorithm for enumerating all its maximal cliques. Assuming that α is the number of maximal cliques of G, our algorithm has setup time O(n(k2 +s(k +1))) and enumeration time αO((k + 1)f(k + 1)) where s(k + 1) (resp. f(k + 1)) is the preprocessing time (resp. enumeration time) for maximal clique enumeration in a general (k + 1)-order graph. This is the first output sensitive algorithm whose enumeration time depends only on the degeneracy of the graph. © 2018 George Manoussakis.

关键词： enumeration algorithms K-degenerate graphs Maximal cliques

来源：评论

学校读者我要写书评

暂无评论

Amortized efficiency of generating planar paths in convex position

引用

THEORETICAL COMPUTER SCIENCE 2011年第35期412卷 4504-4512页

作者： Wu, Ro-Yu Chang, Jou-Ming Pai, Kung-Jui Wang, Yue-Li Natl Taipei Coll Business Inst Informat & Decis Sci Taipei Taiwan Lunghwa Univ Sci & Technol Dept Ind Management Tao Yuan Taiwan Mingchi Univ Technol Dept Ind Engn & Management Taipei Taiwan Natl Taiwan Univ Sci & Technol Dept Informat Management Taipei Taiwan

Let S be a set of n >= 3 points arranged in convex position in the plane and suppose that all points of S are labeled from I to n in clockwise direction. A planar path P on S is a path whose edges connect all points of S with straight line segments such that no two edges of P cross. Flipping an edge on P means that a new path P' is obtained from P by a single edge replacement. In this paper, we provide efficient algorithms to generate all planar paths. With the help of a loopless algorithm to produce a set of 2-way binary-reflected Gray codes, the proposed algorithms generate the next planar path by means of a flip and such that the number of position changes for points in the path has a constant amortized upper bound. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Amortized analysis Convex position enumeration algorithms Geometric graphs Gray codes Planar paths

来源：评论

学校读者我要写书评

暂无评论

Computing Phylo-k-Mers

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2023年第5期20卷 2889-2897页

作者： Romashchenko, Nikolai Linard, Benjamin Rivals, Eric Pardi, Fabio Univ Montpellier LIRMM CNRS F-34095 Montpellier France Univ Toulouse INRAE UR MIAT F-31320 Castanet Tolosan France

Finding the correct position of new sequences within an established phylogenetic tree is an increasingly relevant problem in evolutionary bioinformatics and metagenomics. Recently, alignment-free approaches for this task have been proposed. One such approach is based on the concept of phylogenetically-informative k-mers or phylo-k-mers for short. In practice, phylo-k-mers are inferred from a set of related reference sequences and are equipped with scores expressing the probability of their appearance in different locations within the input reference phylogeny. Computing phylo-k-mers, however, represents a computational bottleneck to their applicability in real-world problems such as the phylogenetic analysis of metabarcoding reads and the detection of novel recombinant viruses. Here we consider the problem of phylo-k-mer computation: how can we efficiently find all k-mers whose probability lies above a given threshold for a given tree node? We describe and analyze algorithms for this problem, relying on branch-and-bound and divide-and-conquer techniques. We exploit the redundancy of adjacent windows of the alignment to save on computation. Besides computational complexity analyses, we provide an empirical evaluation of the relative performance of their implementations on simulated and real-world data. The divide-and-conquer algorithms are found to surpass the branch-and-bound approach, especially when many phylo-k-mers are found.

关键词： Empirical runtimes enumeration algorithms k-mers phylogenetic placement phylogeny

来源：评论

学校读者我要写书评

暂无评论

Maximal strongly connected cliques in directed graphs: algorithms and bounds

引用

DISCRETE APPLIED MATHEMATICS 2021年 303卷 237-252页

作者： Conte, Alessio Kante, Mamadou Moustapha Uno, Takeaki Wasa, Kunihiro Univ Pisa Pisa Italy Univ Clermont Auvergne CNRS LIMOS Aubiere France Natl Inst Informat Tokyo Japan

Finding communities in the form of cohesive subgraphs is a fundamental problem in network analysis. In domains that model networks as undirected graphs, communities are generally associated with dense subgraphs, and many community models have been proposed. Maximal cliques are arguably the most widely studied among such models, with early works dating back to the '60s, and a continuous stream of research up to the present. In domains that model networks as directed graphs, several approaches for community detection have been proposed, but there seems to be no clear model of cohesive subgraph, i.e., of what a community should look like. We extend the fundamental model of clique to directed graphs, adding the natural constraint of strong connectivity within the clique. We consider in this paper the problem of listing all maximal strongly connected cliques in a directed graph. We first investigate the combinatorial properties of strongly connected cliques and use them to prove that every n-vertex directed graph has at most 3(n/3) maximal strongly connected cliques. We then exploit these properties to produce the first algorithms with polynomial delay for enumerating maximal strongly connected cliques: a first algorithm with polynomial delay and exponential space usage, and a second one, based on reverse-search, with higher (still polynomial) delay but which uses linear space.(1) (C) 2020 Elsevier B.V. All rights reserved.

关键词： enumeration algorithms Bounded delay Directed graphs Community detection Network analytics Maximal cliques

来源：评论

学校读者我要写书评

暂无评论

A note on systems with max-min and max-product constraints

引用

FUZZY SETS AND SYSTEMS 2008年第17期159卷 2272-2277页

作者： Elbassioni, Khaled A. Max Planck Inst Informat Saarbrucken Germany

We consider a system A o x >= b, where A is an element of R-+(mxn) is a non-negative matrix and b is an element of R-+(m) is a non-negative vector over the n-dimensional variable l <= x <= u, where l, u is an element of R-+(n) are lower and upper bounds, respectively, and o is either a max-min or a max-product composition. It is shown that the set of minimal solutions of such systems can be computed in incremental quasi -polynomial time. (C) 2008 Elsevier B.V. All rights reserved.

关键词： systems with fuzzy relation equation constraints enumeration algorithms minimal hitting sets finding all minimal solutions

来源：评论

学校读者我要写书评

暂无评论

From Stars to Diamonds: Counting and Listing Almost Complete Subgraphs in Large Networks

引用

COMPUTER JOURNAL 2023年第6期67卷 2151-2161页

作者： Finocchi, Irene Garcia, Renan Leon Sinaimeri, Blerina Luiss Univ Viale Romania 32 I-00197 Rome Italy Sapienza Univ Rome Via Salaria 113 I-00139 Rome Italy

Listing dense subgraphs is a fundamental task with a variety of network analytics applications. A lot of research has been done focusing on $k$-cliques, i.e. complete subgraphs on $k$ nodes. However, requiring complete connectivity between the nodes of a subgraph may be too restrictive in many real applications. Hence, in this paper, we consider a natural relaxation of cliques, called $k$-diamonds and defined as cliques of size $k$ with one missing edge. We first provide a sequential algorithm that, in $O(nm<^>{(k-1)/2})$ time, counts and lists all the $k$-diamonds in large graphs, for any constant $k \geq 4$. A parallel extension of the sequential algorithm is then proposed and analyzed in a MapReduce-style model, achieving the same local and total space usage of the state-of-the-art algorithms for $k$-cliques. The running time is optimal on dense graphs and $O(\sqrt{m})$ larger than $k$-clique counting if the graph is sparse. Our algorithms compute induced diamonds by analyzing the structure of directed stars formed by the graph nodes and their neighbors.

关键词： clique relaxations dense subgraphs distributed algorithms enumeration algorithms graph mining MapReduce

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：