333 research outputs found
Siegfrid of Eppstein
No full textSiegfrid of Eppstein, Archbp. of Mainz. d. 1249 (orig. is sandstone in Dom, Mainz) Nurnberg Mus.https://digitalcommons.acu.edu/ferguson_photos/2403/thumbnail.jp
Recommended from our members
Non-Crossing Hamiltonian Paths and Cycles in Output-Polynomial Time
No full textWe show that, for planar point sets, the number of non-crossing Hamiltonian paths is polynomially bounded in the number of non-crossing paths, and the number of non-crossing Hamiltonian cycles (polygonalizations) is polynomially bounded in the number of surrounding cycles. As a consequence, we can list the non-crossing Hamiltonian paths or the polygonalizations, in time polynomial in the output size, by filtering the output of simple backtracking algorithms for non-crossing paths or surrounding cycles respectively. To prove these results we relate the numbers of non-crossing structures to two easily-computed parameters of the point set: the minimum number of points whose removal results in a collinear set, and the number of points interior to the convex hull. These relations also lead to polynomial-time approximation algorithms for the numbers of structures of all four types, accurate to within a constant factor of the logarithm of these numbers
Recommended from our members
Non-Euclidean Erdős-Anning Theorems
No full textThe Erdős-Anning theorem states that every point set in the Euclidean plane with integer distances must be either collinear or finite. More strongly, for any (non-degenerate) triangle of diameter δ, at most O(δ²) points can have integer distances from all three triangle vertices. We prove the same results for any strictly convex distance function on the plane, and analogous results for every two-dimensional complete Riemannian manifold of bounded genus and for geodesic distance on the boundary of every three-dimensional Euclidean convex set. As a consequence, we resolve a 1983 question of Richard Guy on the equilateral dimension of Riemannian manifolds. Our proofs are based on the properties of additively weighted Voronoi diagrams of these distances
Listing all maximal cliques in sparse graphs in near-optimal time
No full textThe degeneracy of an -vertex graph is the smallest number such that every subgraph of contains a vertex of degree at most . We show that there exists a nearly-optimal fixed-parameter tractable algorithm for enumerating all maximal cliques, parametrized by degeneracy. To achieve this result, we modify the classic Bron--Kerbosch algorithm and show that it runs in time . We also provide matching upper and lower bounds showing that the largest possible number of maximal cliques in an -vertex graph with degeneracy (when is a multiple of 3 and ) is . Therefore, our algorithm matches the worst-case output size of the problem whenever
Sparse dynamic programming I: linear cost functions
No full textDynamic programming solutions to a number of different recurrence equations for sequence comparison and for RNA secondary structure prediction are considered. These recurrences are defined over a number of points that is quadratic in the input size; however only a sparse set matters for the result. Efficient algorithms for these problems are given, when the weight functions used in the recurrences are taken to be linear. The time complexity of the algorithms depends almost linearly on the number of points that need to be considered; when the problems are sparse this results in a substantial speed-up over known algorithms
Sparsification: A technique for speeding up dynamic graph algorithms
No full textWe provide data structures that maintain a graph as edges are inserted and deleted, and
keep track of the following properties with the following times: minimum spanning forests, graph
connectivity, graph 2-edge connectivity, and bipartiteness in time O(n1/2) per change; 3-edge
connectivity, in time O(n2/3) per change; 4-edge connectivity, in time O(na(n)) per change; k-edge
connectivity for constant k, in time O(nlogn) per change; 2-vertex connectivity, and 3-vertex
connectivity, in time O(n) per change; and 4-vertex connectivity, in time O(na(n)) per change
Separator based sparsification I: planarity testing and minimum spanning trees
No full textWe describe algorithms and data structures for maintaining a dynamic planar graph subject to edge insertions and edge deletions that preserve planarity but that can change the embedding. We give a fully dynamic planarity testing algorithm that maintains a graph subject to edge insertions and deletions and that allows queries that test whether the graph is currently planar, or whether a potential new edge would violate planarity, inO(n1/2) amortized time per update or query. We give fully dynamic algorithms for maintaining the connected components, the best swap and the minimum spanning forest of a planar graph inO(log n) worst-case time per insertion andO(log2 n) per deletion. Finally, we give fully dynamic algorithms for maintaining the 2-edge-connected components of a planar graph inO(log n) amortized time per insertion andO(log2 n) per deletion. All of the data structures, except for the one that answers planarity queries, handle only insertions that keep the graph planar. All our algorithms improve previous bounds. The improvements are based upon a new type of sparsification combined with several properties of separators in planar graphs
Separator based sparsification II: edge and vertex connectivity
No full textWe consider the problem of maintaining a dynamic planar graph subject to edge insertions and edge deletions that preserve planarity but that can change the embedding. We describe algorithms and data structures for maintaining information about 2- and 3-vertex-connectivity, and 3- and 4-edge-connectivity in a planar graph in O(n1/2) amortized time per insertion, deletion, or connectivity query. All of the data structures handle insertions that keep the graph planar without regard to any particular embedding of the graph. Our algorithms are based on a new type of sparsification combined with several properties of separators in planar graphs
- …
