In this paper, we consider enumeration problems for edge-distinct and vertex-distinct Eulerian trails. Two Eulerian trails are said to be edge-distinctif the edge sequences are not identical, and they are said to be v...
详细信息
In this paper, we consider enumeration problems for edge-distinct and vertex-distinct Eulerian trails. Two Eulerian trails are said to be edge-distinctif the edge sequences are not identical, and they are said to be vertex-distinctif the vertex sequences are not identical. To solve these problems, we propose optimal enumeration algorithms that run in O(N+ m) total time, where Nis the number of solutions and mis the number of edges in an input connected graph. The proposed algorithms are based on the reverse search technique introduced by [Avis and Fukuda, DAM 1996], and the push-out amortization technique introduced by [Uno, WADS 2015]. (c) 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://***/licenses/by/4.0/).
Terrain visibility graphs are a well-known graph class in computational geometry. They are closely related to polygon visibility graphs, but a precise graph-theoretical characterization is still unknown. Over the last...
详细信息
Terrain visibility graphs are a well-known graph class in computational geometry. They are closely related to polygon visibility graphs, but a precise graph-theoretical characterization is still unknown. Over the last decade, terrain visibility graphs attracted considerable attention in the context of time series analysis (there called time series visibility graphs) with various practical applications in areas such as physics, geography, and medical sciences. Computing shortest paths in visibility graphs is a common task, for example, in line-of-sight communication. For time series analysis, graph characteristics involving shortest paths lengths (such as centrality measures) have proven useful. In this paper, we devise a fast output-sensitive shortest path algorithm on a superclass of terrain visibility graphs called terrain-like graphs (including all induced subgraphs of terrain visibility graphs). Our algorithm runs in O(d * log Delta) time, where d* is the length (that is, the number of edges) of the shortest path and Delta is the maximum vertex degree. Alternatively, with an O(n(2))-time preprocessing our algorithm runs in O(d*) time.
作者：
Rada, MiroslavCerny, MichalUniv Econ
Fac Finance & Accounting Nam W Churchilla 4 Prague 13067 3 Czech Republic Univ Econ
Fac Informat & Stat Nam W Churchilla 4 Prague 13067 3 Czech Republic
We design a new algorithm, called Incremental Enumeration (IncEnu), for the enumeration of full-dimensional cells of hyperplane arrangements (or dually, for the enumeration of vertices of generator-presented zonotopes...
详细信息
We design a new algorithm, called Incremental Enumeration (IncEnu), for the enumeration of full-dimensional cells of hyperplane arrangements (or dually, for the enumeration of vertices of generator-presented zonotopes). The algorithm is based on an incremental construction of the graph of cells of the arrangement. IncEnu is compared to Avis and Fukuda's Reverse Search (RS), including its later improvements by Sleumer and others. The basic versions of IncEnu and RS are not directly comparable, since they solve different numbers of linear programs (LPs) of different sizes. We therefore reformulate our algorithm as a version that permits comparison with RS in terms of the number of LPs solved. The result is that both IncEnu and RS have "the same" complexity-theoretic properties (compactness, output-polynomiality, worst-case bounds, tightness of bounds). In spite of the fact that IncEnu and RS have the same asymptotic bounds, it is proved that IncEnu is faster than RS by a nontrivial additive term. Our computational experiments show that for most test cases IncEnu is significantly faster than RS in practice. Based on the results obtained, we conjecture that IncEnu is O(d) times faster for nondegenerate arrangements, where d denotes the dimension of the arrangement.
We consider the directed Steiner network problem, where given a weighted directed graph G and p pairs of vertices P = {(s(1), t(1)), . . . ,(s(p), t(p))}, one has to find the minimum weight subgraph H of G that contai...
详细信息
We consider the directed Steiner network problem, where given a weighted directed graph G and p pairs of vertices P = {(s(1), t(1)), . . . ,(s(p), t(p))}, one has to find the minimum weight subgraph H of G that contains path from s(i) to t(i) for all i. We search for the main cause of the complexity of the problem and introduce the notions of junction vertex and shared segment in an optimal solution. We study the parameterized complexity of the problem with respect to these parameters and achieve several parameterized hardness results. Also, we present two output-sensitive algorithms for the problem, which are much simpler and easier to implement than the previously best known one;and in addition, when the paths corresponding to the input pairs have few shared vertices or arcs in the optimal solution, these algorithms outperform the previous one.
We use randomness to exploit the potential sparsity of the Boolean matrix product in order to speed up the computation of the product. Our new fast outputsensitivealgorithm for Boolean matrix product and its witnesse...
详细信息
We use randomness to exploit the potential sparsity of the Boolean matrix product in order to speed up the computation of the product. Our new fast outputsensitivealgorithm for Boolean matrix product and its witnesses is randomized and provides the Boolean product and its witnesses almost certainly. Its worst-case time performance is expressed in terms of the input size and the number of non-zero entries of the product matrix. It runs in time (O) over tilde (n(2)s(omega/2-1)), where the input matrices have size nxn, the number of non-zero entries in the product matrix is at most s, omega is the exponent of the fast matrix multiplication and (O) over tilde (f(n)) denotes O(f(n)log(d) n) for some constant d. By the currently best bound on., its running time can be also expressed as (O) over tilde (n(2)s(0.188)). Our algorithm is substantially faster than the output-sensitive column-row method for Boolean matrix product for s larger than n(1.232) and it is never slower than the fast (O) over tilde (n(omega))-time algorithm for this problem. By applying the fast rectangular matrix multiplication, we can refine our upper bound further to the form (O) over tilde (n(omega(1/2) (logns, 1,1))), where omega(p, q, t) is the exponent of the fast multiplication of an n(p) x n(q) matrix by an n(q) x n(t) matrix. We also present a partial derandomization of our algorithm as well as its generalization to include the Boolean product of rectangular Boolean matrices. Finally, we show several applications of our output-sensitive algorithms.
Subgraph isomorphism is a fundamental problem in graph theory. In this paper we focus on listing subgraphs isomorphic to a given pattern graph. First, we look at the algorithm due to Chiba and Nishizeki for listing co...
详细信息
Subgraph isomorphism is a fundamental problem in graph theory. In this paper we focus on listing subgraphs isomorphic to a given pattern graph. First, we look at the algorithm due to Chiba and Nishizeki for listing complete subgraphs of fixed size, and show that it cannot be extended to general subgraphs of fixed size. Then, we consider the algorithm due to Gasieniec et al. for finding multiple witnesses of a Boolean matrix product, and use it to design a new output-sensitive algorithm for listing all triangles in a graph. As a corollary, we obtain an output-sensitive algorithm for listing subgraphs and induced subgraphs isomorphic to an arbitrary fixed pattern graph.
The farthest line-segment Voronoi diagram illustrates properties surprisingly different from its counterpart for points: Voronoi regions may be disconnected and they are not characterized by convex-hull properties. In...
详细信息
The farthest line-segment Voronoi diagram illustrates properties surprisingly different from its counterpart for points: Voronoi regions may be disconnected and they are not characterized by convex-hull properties. In this paper we introduce the farthest hull and its Gaussian map as a closed polygonal curve that characterizes the regions of the farthest line-segment Voronoi diagram, and derive tighter bounds on the (linear) size of this diagram. With the purpose of unifying construction algorithms for farthest-point and farthest line-segment Voronoi diagrams, we adapt standard techniques to construct a convex hull and compute the farthest hull in O(n log n) or outputsensitive O(n log h) time, where n is the number of line-segments and his the number of faces in the corresponding farthest Voronoi diagram. As a result, the farthest line-segment Voronoi diagram can be constructed in outputsensitive O(n log h) time. Our algorithms are given in the Euclidean plane but they hold also in the general L-p metric, 1 <= p <= infinity.
Suppose a given set of n intervals contains a maximum independent set of k disjoint intervals. This brief note demonstrates that "divide and conquer with pruning" produces an easy, output-sensitive O(n log k...
详细信息
Suppose a given set of n intervals contains a maximum independent set of k disjoint intervals. This brief note demonstrates that "divide and conquer with pruning" produces an easy, output-sensitive O(n log k)-time algorithm to compute such a maximum independent set. (c) 2006 Wiley Periodicals, Inc.
Frequent closed pattern discovery is one of the most important topics in the studies of the compact representation for data mining. In this paper, we consider the frequent closed pattern discovery problem for a class ...
详细信息
ISBN:
(纸本)3540281770
Frequent closed pattern discovery is one of the most important topics in the studies of the compact representation for data mining. In this paper, we consider the frequent closed pattern discovery problem for a class of structured data, called attribute trees (AT), which is a subclass of labeled ordered trees and can be also regarded as a fragment of description logic with functional roles only. We present an efficient algorithm for discovering all frequent closed patterns appearing in a given collection of attribute trees. By using a new enumeration method, called the prefix-preserving closure extension, which enable efficient depth-first search over all closed patterns without duplicates, we show that this algorithm works in polynomial time both in the total size of the input database and the number of output trees generated by the algorithm. To our knowledge, this is one of the first result for output-sensitive algorithms for frequent closed substructure disocvery from trees and graphs.
We address the problem of computing homotopic shortest paths in the presence of obstacles in the plane. Problems on homotopy of paths received attention very recently [Cabello et al., in: Proc. 18th Annu. ACM Sympos. ...
详细信息
We address the problem of computing homotopic shortest paths in the presence of obstacles in the plane. Problems on homotopy of paths received attention very recently [Cabello et al., in: Proc. 18th Annu. ACM Sympos. Comput. Geom., 2002, pp. 160-169;Efrat et al., in: Proc. 10th Annu. European Sympos. algorithms, 2002, pp. 411-423]. We present two output-sensitive algorithms, for simple paths and non-simple paths. The algorithm for simple paths improves the previous algorithm [Efrat et al., in: Proc. 10th Annu. European Sympos. algorithms, 2002, pp. 411-423]. The algorithm for non-simple paths achieves O (log(2) n) time per output vertex which is an improvement by a factor of O (n/log(2)n) of the previous algorithm [Hershberger, Snoeyink, Comput. Geom. Theory Appl. 4 (1994) 63-981, where n is the number of obstacles. The running time has an overhead O (n(2+epsilon)) for any positive constant e. In the case k < n2+e, where k is the total size of the input and output, we improve the running to O((n + k + (nk)(2/3)) log(O(1)) n). (C) 2003 Elsevier Inc. All rights reserved.
暂无评论