Improved Algorithms for Constructing Fault-Tolerant Spanners

Let S be a set of n points in a metric space, and let k be a positive integer. Algorithms are given that construct k -fault-tolerant spanners for S . If in such a spanner at most k vertices and/ or edges are removed, then each pair of points in the remaining graph is still connected by a ``short'' path. First, an algorithm is given that transforms an arbitrary spanner into a k -fault-tolerant spanner. For the Euclidean metric in R ^d , this leads to an O(n log n + c ^k n) -time algorithm that constructs a k -fault-tolerant spanner of degree O(c ^k ) , whose total edge length is O(c ^k ) times the weight of a minimum spanning tree of S , for some constant c . For constant values of k , this result is optimal. In the second part of the paper, algorithms are presented for the Euclidean metric in R ^d . These algorithms construct (i) in O(n log n + k ² n) time, a k -fault-tolerant spanner with O(k ² n) edges, and (ii) in O(k n log n) time, such a spanner with O(k n log n) edges.     

A faster algorithm for finding edge-disjoint branchings

An O(k²mn) algorithm is proposed for finding k edge-disjoint branchings in a directed multigraph with m edges and n vertices. With appropriate preprocessing the time bound can be reduced to O(kmn + k³n²). Our proposed algorithm runs faster than any previously known algorithm and provides yet another constructive proof of Edmonds' Branchings Theorem.     

Smallest k-point enclosing rectangle and square of arbitrary orientation

Given a set of n points in 2D, the problem of identifying the smallest rectangle of arbitrary orientation, and containing exactly k(?n) points is studied in this paper. The worst case time and space complexities of the proposed algorithm are O(n²logn+nk(n−k)(n−k+logk)) and O(n), respectively. The algorithm is then used to identify the smallest square of arbitrary orientation, and containing exactly k points in O(n²logn+kn²(n−k)logn) time.     

Order-k voronoi diagrams of sites with additive weights in the plane

It is shown that the order-k Voronoi diagram of n sites with additive weights in the plane has at most (4k?2)(n?k) vertices, (6k?3)(n?k) edges, and (2k?1)(n?itk) + 1 regions. These bounds are approximately the same as the ones known for unweighted order-k Voronoi diagrams. Furthermore, tight upper bounds on the number of edges and vertices are given for the case that every weighted site has a nonempty region in the order-1 diagram. The proof is based on a new algorithm for the construction of these diagrams which generalizes a plane-sweep algorithm for order-1 diagrams developed by Steven Fortune. The new algorithm has time-complexityO(k ² n logn) and space-complexityO(kn). It is the only nontrivial algorithm known for constructing order-kc Voronoi diagrams of sites withadditive weights. It is fairly simple and of practical interest also in the special case of unweighted sites.     

A note on maximum independent sets in rectangle intersection graphs

Finding the maximum independent set in the intersection graph of n axis-parallel rectangles is NP-hard. We re-examine two known approximation results for this problem. For the case of rectangles of unit height, Agarwal, van Kreveld and Suri [Comput. Geom. Theory Appl. 11 (1998) 209-218] gave a (1+1/k)-factor algorithm with an O(nlogn+n^2k−1) time bound for any integer constant k?1; we describe a similar algorithm running in only O(nlogn+nΔ^k−1) time, where Δ?n denotes the maximum number of rectangles a point can be in. For the general case, Berman, DasGupta, Muthukrishnan and Ramaswami [J. Algorithms 41 (2001) 443-470] gave a ⌈log_kn⌉-factor algorithm with an O(n^k+1) time bound for any integer constant k?2; we describe similar algorithms running in O(nlogn+nΔ^k−2) and n^O(k/logk) time.     

A recursive algorithm for quick and efficient bit reversing

An algorithm to generate the permutation by bit reversal of the sequence of integers (0, 1,…,2ⁿ ? 1) is presented. To generate a sequence of length k = 2ⁿ the algorithm requires only k ? 1 additions and k ? 2 multiplications by 2. With respect to previous methods, the reduction of the computing time is O(log₂k).     

Fully Dynamic Geometric Spanners

In this paper we present an algorithm for maintaining a spanner over a dynamic set of points in constant doubling dimension metric spaces. For a set S of points in ? ^d , a t-spanner is a sparse graph on the points of S such that there is a path in the spanner between any pair of points whose total length is at most t times the distance between the points. We present the first fully dynamic algorithm for maintaining a spanner whose update time depends solely on the number of points in S. In particular, we show how to maintain a (1+ε)-spanner with O(n/ε ^d ) edges, where points can be inserted to S in an amortized update time of O(log?n) and deleted from S in an amortized update time of $\tilde{O}(n^{1/3})$ . As a by-product of our techniques we obtain a simple incremental algorithm for constructing a (1+ε)-spanner with O(n/ε ^d ) edges in constant doubling dimension metric spaces whose running time is O(nlog?n).     

Incremental labeling in closed-2PM model

We consider an incremental optimal label placement in a closed-2PM map containing points each attached with a label. Labels are assumed to be axis-parallel square-shaped and have to be pairwise disjoint with maximum possible length each attached to its corresponding point on one of its horizontal edges. Such a labeling is denoted as optimal labeling. Our goal is to efficiently generate a new optimal labeling for all points after each new point being inserted in the map. Inserting each point may require several labels to flip or all labels to shrink. We present an algorithm that generates each new optimal labeling in O(lgn+k) time where k is the number of required label flips, if there is no need to shrink the label lengths, or in O(n) time when we have to shrink the labels and flip some of them. The algorithm uses O(n) space in both cases. This is a new result on this problem.     

A Probabilistic Algorithm for k -SAT Based on Limited Local Search and Restart

A simple probabilistic algorithm for solving the NP-complete problem k -SAT is reconsidered. This algorithm follows a well-known local-search paradigm: randomly guess an initial assignment and then, guided by those clauses that are not satisfied, by successively choosing a random literal from such a clause and changing the corresponding truth value, try to find a satisfying assignment. Papadimitriou [11] introduced this random approach and applied it to the case of 2-SAT, obtaining an expected O(n ² ) time bound. The novelty here is to restart the algorithm after 3n unsuccessful steps of local search. The analysis shows that for any satisfiable k -CNF formula with n variables the expected number of repetitions until a satisfying assignment is found this way is (2? (k-1)/ k) ⁿ . Thus, for 3-SAT the algorithm presented here has a complexity which is within a polynomial factor of (\frac 4 3 ) ⁿ . This is the fastest and also the simplest among those algorithms known up to date for 3-SAT achieving an o(2 ⁿ ) time bound. Also, the analysis is quite simple compared with other such algorithms considered before.     

Fully dynamic biconnectivity in graphs

We present an algorithm for maintaining the biconnected components of a graph during a sequence of edge insertions and deletions. It requires linear storage and preprocessing time. The amortized running time for insertions and for deletions isO(m ^2/3 ), wherem is the number of edges in the graph. Any query of the form ‘Are the verticesu andv biconnected?’ can be answered in timeO(1). This is the first sublinear algorithm for this problem. We can also output all articulation points separating any two vertices efficiently. If the input is a plane graph, the amortized running time for insertions and deletions drops toO(√n logn) and the query time isO(log² n), wheren is the number of vertices in the graph. The best previously known solution takes timeO(n ^2/3 ) per update or query.     

Computing shortest transversals

We present anO(nlog² n) time andO(n) space algorithm for computing the shortest line segment that intersects a set ofn given line segments or lines in the plane. If the line segments do not intersect the algorithm may be trimmed to run inO(nlogn) time. Furthermore, in combination with linear programming the algorithm will also find the shortest line segment that intersects a set ofn isothetic rectangles in the plane inO(nlogk) time, wherek is the combinatorial complexity of the space of transversals andk≤4n. These results find application in: (1) line-fitting between a set ofn data ranges where it is desired to obtain the shortestline-of-fit, (2) finding the shortest line segment from which a convexn-vertex polygon is weakly externally visible, and (3) determing the shortestline-of-sight between two edges of a simplen-vertex polygon, for whichO(n) time algorithms are also given. All the algorithms are based on the solution to a new fundamental geometric optimization problem that is of independent interest and should find application in different contexts as well.     

Improved Algorithms for Constructing Fault-Tolerant Spanners

Abstract. Let S be a set of n points in a metric space, and let k be a positive integer. Algorithms are given that construct k -fault-tolerant spanners for S . If in such a spanner at most k vertices and/ or edges are removed, then each pair of points in the remaining graph is still connected by a ``short' path. First, an algorithm is given that transforms an arbitrary spanner into a k -fault-tolerant spanner. For the Euclidean metric in R ^d , this leads to an O(n log n + c ^k n) -time algorithm that constructs a k -fault-tolerant spanner of degree O(c ^k ) , whose total edge length is O(c ^k ) times the weight of a minimum spanning tree of S , for some constant c . For constant values of k , this result is optimal. In the second part of the paper, algorithms are presented for the Euclidean metric in R ^d . These algorithms construct (i) in O(n log n + k ² n) time, a k -fault-tolerant spanner with O(k ² n) edges, and (ii) in O(k n log n) time, such a spanner with O(k n log n) edges.     

An Algorithm for Minimum Cost Arc-Connectivity Orientations

Given a 2k-edge-connected undirected graph, we consider to find a minimum cost orientation that yields a k-arc-connected directed graph. This minimum cost k-arc-connected orientation problem is a special case of the submodular flow problem. Frank (1982) devised a combinatorial algorithm that solves the problem in O(k ² n ³ m) time, where n and m are the numbers of vertices and edges, respectively. Gabow (1995) improved Frank’s algorithm to run in O(kn ² m) time by introducing a new sophisticated data structure. We describe an algorithm that runs in O(k ³ n ³+kn ² m) time without using sophisticated data structures. In addition, we present an application of the algorithm to find a shortest dijoin in O(n ² m) time, which matches the current best bound.     

Preprocess, Set, Query!

Thorup and Zwick (J. ACM 52(1):1–24, 2005 and STOC’01) in their seminal work introduced the notion of distance oracles. Given an n-vertex weighted undirected graph with m edges, they show that for any integer k≥1 it is possible to preprocess the graph in $\tilde {O}(mn^{1/k})$ time and generate a compact data structure of size O(kn ^1+1/k ). For each pair of vertices, it is then possible to retrieve an estimated distance with multiplicative stretch 2k?1 in O(k) time. For k=2 this gives an oracle of O(n ^1.5) size that produces in constant time estimated distances with stretch 3. Recently, Pǎtra?cu and Roditty (In: Proc. of 51st FOCS, 2010) broke the theoretical status-quo in the field of distance oracles and obtained a distance oracle for sparse unweighted graphs of O(n ^5/3) size that produces in constant time estimated distances with stretch 2. In this paper we show that it is possible to break the stretch 2 barrier at the price of non-constant query time in unweighted undirected graphs. We present a data structure that produces estimated distances with 1+ε stretch. The size of the data structure is O(nm ^1?ε′) and the query time is $\tilde {O}(m^{1-\varepsilon '})$ . Using it for sparse unweighted graphs we can get a data structure of size O(n ^1.87) that can supply in O(n ^0.87) time estimated distances with multiplicative stretch 1.75.     

Selection in X + Y and matrices with sorted rows and columns

Let A be an n×n matrix of reals with sorted rows and columns and k an integer, 1 ? k ? n². We present an O(n) time algorithm for selecting the kth smallest element of A. If X and Y are sorted n-vectors of reals, then Cartesian sum X + Y is such a matrix as A. One application of selection in X + Y can be found in statistics. The algorithm presented here is based on a new divide-and-conquer technique, which can be applied to similar order related problems as well. Due to the fact that the algorithm has a relatively small constant time factor, this result is of practical as well as theoretical interest.     

Computing Optimal Steiner Trees in Polynomial Space

Given an n-node edge-weighted graph and a subset of k terminal nodes, the NP-hard (weighted) Steiner tree problem is to compute a minimum-weight tree which spans the terminals. All the known algorithms for this problem which improve on trivial O(1.62 ⁿ )-time enumeration are based on dynamic programming, and require exponential space. Motivated by the fact that exponential-space algorithms are typically impractical, in this paper we address the problem of designing faster polynomial-space algorithms. Our first contribution is a simple O((27/4) ^k n ^O(logk))-time polynomial-space algorithm for the problem. This algorithm is based on a variant of the classical tree-separator theorem: every Steiner tree has a node whose removal partitions the tree in two forests, containing at most 2k/3 terminals each. Exploiting separators of logarithmic size which evenly partition the terminals, we are able to reduce the running time to $O(4^{k}n^{O(\log^{2} k)})$ . This improves on trivial enumeration for roughly k<n/3, which covers most of the cases of practical interest. Combining the latter algorithm (for small k) with trivial enumeration (for large k) we obtain a O(1.59 ⁿ )-time polynomial-space algorithm for the weighted Steiner tree problem. As a second contribution of this paper, we present a O(1.55 ⁿ )-time polynomial-space algorithm for the cardinality version of the problem, where all edge weights are one. This result is based on a improved branching strategy. The refined branching is based on a charging mechanism which shows that, for large values of k, convenient local configurations of terminals and non-terminals exist. The analysis of the algorithm relies on the Measure & Conquer approach: the non-standard measure used here is a linear combination of the number of nodes and number of non-terminals. Using a recent result in Nederlof (International colloquium on automata, languages and programming (ICALP), pp. 713–725, 2009), the running time can be reduced to O(1.36 ⁿ ). The previous best algorithm for the cardinality case runs in O(1.42 ⁿ ) time and exponential space.     

A faster parameterized algorithm for set packing

We present an efficient parameterized algorithm for the (k,t)-set packing problem, in which we are looking for a collection of k disjoint sets whose union consists of t elements. The complexity of the algorithm is O(²O(t)nNlogN). For the special case of sets of bounded size, this improves the O(k(ck)n) algorithm of Jia et al. [J. Algorithms 50 (1) (2004) 106].     

Fast Parallel Reordering and Isomorphism Testing of k -Trees

In this paper two problems on the class of k -trees, a subclass of the class of chordal graphs, are considered: the fast reordering problem and the isomorphism problem. An O(log ² n) time parallel algorithm for the fast reordering problem is described that uses O(nk(n-k)/\kern -1ptlog n) processors on a CRCW PRAM proving membership in the class NC for fixed k . An O(nk(k+1)!) time sequential algorithm for the isomorphism problem is obtained representing an improvement over the O(n ² k(k+1)!) algorithm of Sekharan (the second author) [10]. A parallel version of this sequential algorithm is presented that runs in O(log ² n) time using O((nk((k+1)!+n-k))/log n) processors improving on a parallel algorithm of Sekharan for the isomorphism problem [10]. Both the sequential and parallel algorithms use a concept introduced in this paper called the kernel of a k -tree.     

Chromatic distribution of k-nearest neighbors of a line segment in a planar colored point set

Let P be a set of n colored points distributed arbitrarily in R². The chromatic distribution of the k-nearest neighbors of a query line segment ? is to report the number of points of each color among the k-nearest points of the query line segment. While solving this problem, we have encountered another interesting problem, namely the semicircular range counting query. Here a set of n points is given. The objective is to report the number of points inside a given semicircular range. We propose a simple algorithm for this problem with preprocessing time and space complexity O(n³), and the query time complexity O(logn). Finally, we propose the algorithm for reporting the chromatic distribution of k nearest neighbors of a query line segment. Using our proposed technique for semicircular range counting query, it runs in O(log²n) time.     

Note on covering monotone orthogonal polygons with star-shaped polygons

In 1986, Keil provided an O(n²) time algorithm for the problem of covering monotone orthogonal polygons with the minimum number of r-star-shaped orthogonal polygons. This was later improved to O(n) time and space by Gewali et al. in [L. Gewali, M. Keil, S.C. Ntafos, On covering orthogonal polygons with star-shaped polygons, Information Sciences 65 (1992) 45-63]. In this paper we simplify the latter algorithm—we show that with a little modification, the first step Sweep1 of the discussed algorithm—which computes the top ceilings of horizontal grid segments—can be omitted.In addition, for the minimum orthogonal guard problem in the considered class of polygons, our approach provides a linear time algorithm which uses O(k) additional space, where k is the size of the optimal solution—the algorithm in [L. Gewali, M. Keil, S.C. Ntafos, On covering orthogonal polygons with star-shaped polygons, Information Sciences 65 (1992) 45-63] uses both O(n) time and O(n) additional space.