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...
详细信息
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.
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 B...
详细信息
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.
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. ...
详细信息
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.
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 ne...
详细信息
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...
详细信息
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 point...
详细信息
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.
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 t...
详细信息
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.
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 m...
详细信息
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.
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...
详细信息
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.
Conventional Lagrangean preprocessing for the network Weight Constrained Shortest Path Problem (WCSPP), for example Beasley and Christofides (Beasley and Christofides, Networks 19 (1989)9 379-394), calculates lower bo...
详细信息
Conventional Lagrangean preprocessing for the network Weight Constrained Shortest Path Problem (WCSPP), for example Beasley and Christofides (Beasley and Christofides, Networks 19 (1989)9 379-394), calculates lower bounds on the cost of using each node and edge in a feasible path using a single optimal Lagrange multiplier for the relaxation of the WCSPP. These lower bounds are used in conjunction with an upper bound to eliminate nodes and edges. However, for each node and edge, a Lagrangean dual problem exists whose solution may differ from the relaxation of the full problem. Thus, using one Lagrange multiplier does not offer the best possible network reduction. Furthermore, eliminating nodes and edges from the network may change the Lagrangean dual solutions in the remaining reduced network, warranting an iterative solution and reduction procedure. We develop a method for solving the related Lagrangean dual problems for each edge simultaneously which is iterated with eliminating nodes and edges. We demonstrate the effectiveness of our method computationally: we test it against several others and show that it both reduces solve time and the number of intractable problems encountered. We use a modified version of Carlyle and Wood's (38th Annual ORSNZ Conference, Hamilton, New Zealand, November, 2003) enumeration algorithm in the gap closing stage. We also make improvements to this algorithm and test them computationally. (C) 2009 Wiley Periodicals, Inc. NETWORKS, Vol. 53(4), 358-381 2009
暂无评论