On the Connection Between the Correction and Weighting Functions in the Correction Procedure via Reconstruction Method

In this note, the connection between the correction and weighting functions for the correction procedure via reconstruction (CPR) method in 1D is addressed. A one-parameter family of weighting functions is constructed from the discontinuous test space. It is found that if the solution polynomials lie in the space P ^k , then the first k weighting functions can always be chosen as the basis of the polynomial space P ^k?1 and the last weighting function can be selected as a piece-wise continuous polynomial. There exists at least one set of weighting functions which can recover the energy stable flux reconstruction (ESFR) schemes. This strategy has been successfully applied to recover several known high-order discontinuous schemes, including DG, SD, SV, and Huynh??s g ₂ scheme.     

On the number of higher order Delaunay triangulations

Higher order Delaunay triangulations are a generalization of the Delaunay triangulation that provides a class of well-shaped triangulations, over which extra criteria can be optimized. A triangulation is order-k Delaunay if the circumcircle of each triangle of the triangulation contains at most k points. In this paper we study lower and upper bounds on the number of higher order Delaunay triangulations, as well as their expected number for randomly distributed points. We show that arbitrarily large point sets can have a single higher order Delaunay triangulation, even for large orders, whereas for first order Delaunay triangulations, the maximum number is 2ⁿ⁻³. Next we show that uniformly distributed points have an expected number of at least 2^{ρ₁n(1+o(1))} first order Delaunay triangulations, where ρ₁ is an analytically defined constant (ρ₁≈0.525785), and for k>1, the expected number of order-k Delaunay triangulations (which are not order-i for any i<k) is at least 2^{ρ_kn(1+o(1))}, where ρ_k can be calculated numerically.     

On plane spanning trees and cycles of multicolored point sets with few intersections

Let P₁,…,Pk be a collection of disjoint point sets in R² in general position. We prove that for each 1?i?k we can find a plane spanning tree Ti of Pi such that the edges of T₁,…,Tk intersect at most , where n is the number of points in P₁∪?∪Pk. If the intersection of the convex hulls of P₁,…,Pk is nonempty, we can find k spanning cycles such that their edges intersect at most (k−1)n times, this bound is tight. We also prove that if P and Q are disjoint point sets in general position, then the minimum weight spanning trees of P and Q intersect at most 8n times, where |P∪Q|=n (the weight of an edge is its length).     

Simultaneous inner and outer approximation of shapes

For compact Euclidean bodiesP, Q, we define λ(P, Q) to be the smallest ratior/s wherer > 0,s > 0 satisfy \(sQ' \subseteq P \subseteq rQ''\) . HeresQ denotes a scaling ofQ by the factors, andQ′,Q″ are some translates ofQ. This function λ gives us a new distance function between bodies which, unlike previously studied measures, is invariant under affine transformations. If homothetic bodies are identified, the logarithm of this function is a metric. (Two bodies arehomothetic if one can be obtained from the other by scaling and translation.) For integerk ≥ 3, define λ(k) to be the minimum value such that for each convex polygonP there exists a convexk-gonQ with λ(P, Q) ≤ λ(k). Among other results, we prove that 2.118 ... <-λ(3) ≤ 2.25 and λ(k) = 1 + Θ(k ^?2). We give anO(n ² log² n)-time algorithm which, for any input convexn-gonP, finds a triangleT that minimizes λ(T, P) among triangles. However, in linear time we can find a trianglet with λ(t, P)<-2.25. Our study is motivated by the attempt to reduce the complexity of the polygon containment problem, and also the motion-planning problem. In each case we describe algorithms which run faster when certain implicitslackness parameters of the input are bounded away from 1. These algorithms illustrate a new algorithmic paradigm in computational geometry for coping with complexity.     

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 note on shrinking and expanding operations in pyramids

Simple pyramid algorithms are described that, in O(k) steps, shrink or expand the 1's in a binary image by 2^k − 1 (k = 1,2, …) and resample the results at intervals of 2^k. For a one-dimensional image, the results can be computed without resampling provided the kth step is allowed to involve O(k) computation; but in two dimensions, O(2^k) computation would be required, so that the pyramid has no advantages over a mesh. For grayscale images (with local Min and local Max playing the roles of shrinking and expanding), the resampled computation is still straightforward, but the unresampled computation cannot be done economically even in the one-dimensional case.     

Optimization problems and the polynomial hierarchy

It is demonstrated that such problems as the symmetric Travelling Salesman Problem, Chromatic Number Problem, Maximal Clique Problem and a Knapsack Packing Problem are in the Δ^P₂ level of PH and no lower if ∑^P₁ ≠ Π^P₁, or NP≠co-NP. This shows that these problems cannot be solved by polynomial reductions that use only positive information from an NP oracle, if NP≠co-NP. It is then shown how to extend these results to prove that interesting problems are properly in Δ^P,X_i+1 for all X,k where ∑^P,X_k≠Π^P,X_k in PH^X.     

Graph Isomorphism is in SPP

We show that Graph Isomorphism is in the complexity class SPP, and hence it is in ⊕P (in fact, in Mod_kP for each k ⩾ 2). These inclusions for Graph Isomorphism were not known prior to membership in SPP. We derive this result as a corollary of a more general result: we show that a generic problem FIND-GROUP has an FP^SPP algorithm. This general result has other consequences: for example, it follows that the hidden subgroup problem for permutation groups, studied in the context of quantum algorithms, has an FP^SPP algorithm. Also, some other algorithmic problems over permutation groups known to be at least as hard as Graph Isomorphism (e.g., coset intersection) are in SPP, and thus in Mod_kP for each k ⩾ 2.     

Computing Modular Invariants of p-groups

Let V be a finite dimensional representation of a p -group, G, over a field,k , of characteristic p. We show that there exists a choice of basis and monomial order for which the ring of invariants, k [ V ]^G, has a finite SAGBI basis. We describe two algorithms for constructing a generating set for k [ V ] G. We use these methods to analyse k [2V₃ ]^U₃where U₃is the p -Sylow subgroup ofGL₃ (F_p) and 2 V₃is the sum of two copies of the canonical representation. We give a generating set for k [2 V₃]^U₃forp =  3 and prove that the invariants fail to be Cohen–Macaulay forp >  2. We also give a minimal generating set for k [mV₂ ]^Z / pwere V₂is the two-dimensional indecomposable representation of the cyclic group Z / p.     

Computing the subset partial order for dense families of sets

We give an algorithm to compute the subset partial order (called the subset graph) for a family F of sets containing k sets with N elements in total and domain size n. Our algorithm requires O(nk²/logk) time and space on a Pointer Machine. When F is dense, i.e. N=Θ(nk), the algorithm requires O(N²/log²N) time and space. We give a construction for a dense family whose subset graph is of size Θ(N²/log²N), indicating the optimality of our algorithm for dense families. The subset graph can be dynamically maintained when F undergoes set insertions and deletions in O(nk/logk) time per update (that is sub-linear in N for the case of dense families). If we assume words of b?k bits, allow bits to be packed in words, and use bitwise operations, the above running time and space requirements can be reduced by a factor of blog(k/b+1)/logk and b²log(k/b+1)/logk respectively.     

A New Nonsymmetric Discontinuous Galerkin Method for Time Dependent Convection Diffusion Equations

We propose a discontinuous Galerkin finite element method for convection diffusion equations that involves a new methodology handling the diffusion term. Test function derivative numerical flux term is introduced in the scheme formulation to balance the solution derivative numerical flux term. The scheme has a nonsymmetric structure. For general nonlinear diffusion equations, nonlinear stability of the numerical solution is obtained. Optimal kth order error estimate under energy norm is proved for linear diffusion problems with piecewise P ^k polynomial approximations. Numerical examples under one-dimensional and two-dimensional settings are carried out. Optimal (k+1)th order of accuracy with P ^k polynomial approximations is obtained on uniform and nonuniform meshes. Compared to the Baumann-Oden method and the NIPG method, the optimal convergence is recovered for even order P ^k polynomial approximations.     

An Efficient Algorithm for the k-Pairwise Disjoint Paths Problem in Hypercubes

A graph G(V, E) (|V|⩾2k) satisfies property A_k if, given k pairs of distinct nodes (s₁, t₁), …, (s_k, t_k) of V(G), there are k mutually node-disjoint paths, one connecting s_i and t_i for each i, 1⩽i⩽k. A necessary condition for any graph to satisfy A_k is that it is (2k−1)-connected. Hypercubes are important interconnection topologies for parallel computation and communication networks. It has been known that hypercubes of dimension n (which are n-connected) satisfy A_⌈n/2⌉. In this paper we give an algorithm which, given k=⌈n/2⌉ pairs of distinct nodes (s₁, t₁), …, (s_k, t_k) in the n-dimensional hypercube, finds the k disjoint paths of length at most n+⌈log n⌉+1 in O(n² log* n) time.     

The Space Complexity of Approximating the Frequency Moments

The frequency moments of a sequence containingm_ielements of typei, 1⩽i⩽n, are the numbersF_k=∑ⁿ_i=1 m^k_i. We consider the space complexity of randomized algorithms that approximate the numbersF_k, when the elements of the sequence are given one by one and cannot be stored. Surprisingly, it turns out that the numbersF₀,F₁, andF₂can be approximated in logarithmic space, whereas the approximation ofF_kfork⩾6 requiresn^Ω(1)space. Applications to data bases are mentioned as well.     

Path bipancyclicity of hypercubes

A bipartite graph is vertex-bipancyclic (respectively, edge-bipancyclic) if every vertex (respectively, edge) lies in a cycle of every even length from 4 to |V(G)| inclusive. It is easy to see that every connected edge-bipancyclic graph is vertex-bipancyclic. An n-dimensional hypercube, or n-cube denoted by Qn, is well known as bipartite and one of the most efficient networks for parallel computation. In this paper, we study a stronger bipancyclicity of hypercubes. We prove that every n-dimensional hypercube is (2n−4)-path-bipancyclic for n?3. That is, for any path P of length k with 1?k?2n−4 and any integer l with max{2,k}?l?²n−1, an even cycle C of length 2l can be found in Qn such that the path P is included in C for n?3.     

Linear Differential Operators for Polynomial Equations

Given a squarefree polynomial P ∈ k₀[ x,y ], k₀a number field, we construct a linear differential operator that allows one to calculate the genus of the complex curve defined by P =  0 (when P is absolutely irreducible), the absolute factorization of P over the algebraic closure of k₀, and calculate information concerning the Galois group of P over ___ k₀(x) as well as overk₀ (x).     

A web personalizing technique using adaptive data structures: The case of bursts in web visits

The explosive growth in the size and use of the World Wide Web continuously creates new great challenges and needs. The need for predicting the users’ preferences in order to expedite and improve the browsing though a site can be achieved through personalizing of the Websites. Recommendation and personalization algorithms aim at suggesting WebPages to users based on their current visit and past users’ navigational patterns. The problem that we address is the case where few WebPages become very popular for short periods of time and are accessed very frequently in a limited temporal space. Our aim is to deal with these bursts of visits and suggest these highly accessed pages to the future users that have common interests. Hence, in this paper, we propose a new web personalization technique, based on advanced data structures.The data structures that are used are the Splay tree (1) and Binary heaps (2). We describe the architecture of the technique, analyze the time and space complexity and prove its performance. In addition, we compare both theoretically and experimentally the proposed technique to another approach to verify its efficiency. Our solution achieves O(P²) space complexity and runs in k log P time, where k is the number of pages and P the number of categories of WebPages.     

Faster parameterized algorithms for minor containment

The H-Minor containment problem asks whether a graph G contains some fixed graph H as a minor, that is, whether H can be obtained by some subgraph of G after contracting edges. The derivation of a polynomial-time algorithm for H-Minor containment is one of the most important and technical parts of the Graph Minor Theory of Robertson and Seymour and it is a cornerstone for most of the algorithmic applications of this theory. H-Minor containment for graphs of bounded branchwidth is a basic ingredient of this algorithm. The currently fastest solution to this problem, based on the ideas introduced by Robertson and Seymour, was given by Hicks in [I.V. Hicks, Branch decompositions and minor containment, Networks 43 (1) (2004) 1-9], providing an algorithm that in time O(3^k2⋅(h+k−1)!⋅m) decides if a graph G with m edges and branchwidth k, contains a fixed graph H on h vertices as a minor. In this work we improve the dependence on k of Hicks’ result by showing that checking if H is a minor of G can be done in time O(2^{(2k+1)⋅logk}⋅h^2k⋅2^2h2⋅m). We set up an approach based on a combinatorial object called rooted packing, which captures the properties of the subgraphs of H that we seek in our dynamic programming algorithm. This formulation with rooted packings allows us to speed up the algorithm when G is embedded in a fixed surface, obtaining the first algorithm for minor containment testing with single-exponential dependence on branchwidth. Namely, it runs in time 2^O(k)⋅h^2k⋅2^O(h)⋅n, with n=∣V(G)∣. Finally, we show that slight modifications of our algorithm permit to solve some related problems within the same time bounds, like induced minor or contraction containment.     

New upper and lower bounds for the eigenvalues of the Sturm-Liouville problem

We derive new inequalities for the eigenvaluesλ _k of the Sturm-Liouville problem?u″+qu=λu, u(0)=u(π)=0 under the usual hypothesis thatq has mean value zero. The estimates give upper and lower bounds of the form |λ _k ?k ²|≤p _1,m k ^?m +P _2,m k ^2m ,k ²≥3‖q‖ _m ,m=1, 2 where ‖q‖ _m is the norm ofq in a Sobolev spaceH ^m (0, π) and theP's are homogeneous polynomials of degree at most 3 in ‖q‖ _m . Such bounds are used in the analysis of the inverse Sturm-Liouville problem.     

A randomized clustering of anonymous wireless ad hoc networks with an application to the initialization problem

The Distributed Mobility-Adaptive Clustering (DMAC) due to Basagni partitions the nodes of a mobile ad hoc network into clusters, thus giving the network a hierarchical organization. This algorithm supports the mobility of the nodes, even during the cluster formation. The main feature of DMAC is that in a weighted network (in which two or more nodes cannot have the same weight), nodes have to choose the clusterheads taking into account only the node weight, i.e. the mobility when a node weight is the inverse of its speed. In our approach many nodes may have the same speed and hence the same weight. We assume that nodes have no identities and the number of nodes, say n, is the only known parameter of the network. After the randomized clustering, we show that the initialization problem can be solved in a multi-hop ad hoc wireless network of n stations in O(k ^1/2log ^1/2 k)+D _b −1+O(log (max (P _i )+log ²max (P _i )) broadcast rounds with high probability, where k is the number of clusters, D _b is the blocking diameter and max (P _i ), 1≤i≤k, is the maximum number of nodes in a cluster. Thus the initialization protocol presented here uses less broadcast rounds than the one in Ravelemanana (IEEE Trans. Parallel Distributed Syst. 18(1):17–28 2007).     

Online capacity maximization in wireless networks

In this paper we study a dynamic version of capacity maximization in the physical model of wireless communication. In our model, requests for connections between pairs of points in Euclidean space of constant dimension d arrive iteratively over time. When a new request arrives, an online algorithm needs to decide whether or not to accept the request and to assign one out of k channels and a transmission power to the request. Accepted requests must satisfy constraints on the signal-to-interference-plus-noise (SINR) ratio. The objective is to maximize the number of accepted requests. Using competitive analysis we study algorithms using distance-based power assignments, for which the power of a request relies only on the distance between the points. Such assignments are inherently local and particularly useful in distributed settings. We first focus on the case of a single channel. For request sets with spatial lengths in [1,Δ] and duration in [1,Γ] we derive a lower bound of Ω(Γ?Δ ^d/2) on the competitive ratio of any deterministic online algorithm using a distance-based power assignment. Our main result is a near-optimal deterministic algorithm that is O(Γ?Δ^(d/2)+ε )-competitive, for any constant ε>0. Our algorithm for a single channel can be generalized to k channels. It can be adjusted to yield a competitive ratio of O(k?Γ ^1/k′?Δ^(d/2k″)+ε ) for any factorization (k′,k″) such that k′?k″=k. This illustrates the effectiveness of multiple channels when dealing with unknown request sequences. In particular, for Θ(log?Γ?log?Δ) channels this yields an O(log?Γ?log?Δ)-competitive algorithm. Additionally, we show how this approach can be turned into a randomized algorithm, which is O(log?Γ?log?Δ)-competitive even for a single channel.