Analysing local algorithms in location-aware quasi-unit-disk graphs

A local algorithm with local horizon r is a distributed algorithm that runs in r synchronous communication rounds; here r is a constant that does not depend on the size of the network. As a consequence, the output of a node in a local algorithm only depends on the input within r hops from the node. We give tight bounds on the local horizon for a class of local algorithms for combinatorial problems on unit-disk graphs (UDGs). Most of our bounds are due to a refined analysis of existing approaches, while others are obtained by suggesting new algorithms. The algorithms we consider are based on network decompositions guided by a rectangular tiling of the plane. The algorithms are applied to matching, independent set, graph colouring, vertex cover, and dominating set. We also study local algorithms on quasi-UDGs, which are a popular generalisation of UDGs, aimed at more realistic modelling of communication between the network nodes. Analysing the local algorithms on quasi-UDGs allows one to assume that the nodes know their coordinates only approximately, up to an additive error. Despite the localisation error, the quality of the solution to problems on quasi-UDGs remains the same as for the case of UDGs with perfect location awareness. We analyse the increase in the local horizon that comes along with moving from UDGs to quasi-UDGs.

Evaluation of a boundary integral representation for the conformal mapping of the unit disk onto a simply-connected domain

A representation of the conformal mapping g of the interior or exterior of the unit circle onto a simply-connected domain Ω as a boundary integral in terms ofƒ|∂Ω is obtained, whereƒ :=g -l. A product integration scheme for the approximation of the boundary integral is described and analysed. An ill-conditioning problem related to the domain geometry is discussed. Numerical examples confirm the conclusions of this discussion and support the analysis of the quadrature scheme.

Planar subgraphs without low-degree nodes

We study the following problem: given a geometric graph G and an integer k, determine if G has a planar spanning subgraph (with the original embedding and straight-line edges) such that all nodes have degree at least k. If G is a unit disk graph, the problem is trivial to solve for k = 1. We show that even the slightest deviation from the trivial case (e.g., quasi unit disk graphs or k = 1) leads to NP-hard problems.

Rozproszone algorytmy aproksymacyjne dla grafów dyskowych

Wydział Matematyki i Informatyki: Zakład Matematyki Dyskretnej

A constant factor approximation algorithm for boxicity of circular arc graphs

The boxicity (resp. cubicity) of a graph G(V, E) is the minimum integer k such that G can be represented as the intersection graph of axis parallel boxes (resp. cubes) in R-k. Equivalently, it is the minimum number of interval graphs (resp. unit interval graphs) on the vertex set V, such that the intersection of their edge sets is E. The problem of computing boxicity (resp. cubicity) is known to be inapproximable, even for restricted graph classes like bipartite, co-bipartite and split graphs, within an O(n(1-epsilon))-factor for any epsilon > 0 in polynomial time, unless NP = ZPP. For any well known graph class of unbounded boxicity, there is no known approximation algorithm that gives n(1-epsilon)-factor approximation algorithm for computing boxicity in polynomial time, for any epsilon > 0. In this paper, we consider the problem of approximating the boxicity (cubicity) of circular arc graphs intersection graphs of arcs of a circle. Circular arc graphs are known to have unbounded boxicity, which could be as large as Omega(n). We give a (2 + 1/k) -factor (resp. (2 + log n]/k)-factor) polynomial time approximation algorithm for computing the boxicity (resp. cubicity) of any circular arc graph, where k >= 1 is the value of the optimum solution. For normal circular arc (NCA) graphs, with an NCA model given, this can be improved to an additive two approximation algorithm. The time complexity of the algorithms to approximately compute the boxicity (resp. cubicity) is O(mn + n(2)) in both these cases, and in O(mn + kn(2)) = O(n(3)) time we also get their corresponding box (resp. cube) representations, where n is the number of vertices of the graph and m is its number of edges. Our additive two approximation algorithm directly works for any proper circular arc graph, since their NCA models can be computed in polynomial time. (C) 2014 Elsevier B.V. All rights reserved.

On computational aspects of discrete Sobolev inner products on the unit circle

In this paper, we show how to compute in O(n2) steps the Fourier coefficients associated with the Gelfand-Levitan approach for discrete Sobolev orthogonal polynomials on the unit circle when the support of the discrete component involving derivatives is located outside the closed unit disk. As a consequence, we deduce the outer relative asymptotics of these polynomials in terms of those associated with the original orthogonality measure. Moreover, we show how to recover the discrete part of our Sobolev inner product. © 2013 Elsevier Inc. All rights reserved.

A preconditioned Lanczos method for space-fractional reaction-diffusion equations on two-dimensional unstructured meshes

We consider a two-dimensional space-fractional reaction diffusion equation with a fractional Laplacian operator and homogeneous Neumann boundary conditions. The finite volume method is used with the matrix transfer technique of Ilić et al. (2006) to discretise in space, yielding a system of equations that requires the action of a matrix function to solve at each timestep. Rather than form this matrix function explicitly, we use Krylov subspace techniques to approximate the action of this matrix function. Specifically, we apply the Lanczos method, after a suitable transformation of the problem to recover symmetry. To improve the convergence of this method, we utilise a preconditioner that deflates the smallest eigenvalues from the spectrum. We demonstrate the efficiency of our approach for a fractional Fisher’s equation on the unit disk.

Composition operators on vector-valued BMOA and related function spaces

A composition operator is a linear operator between spaces of analytic or harmonic functions on the unit disk, which precomposes a function with a fixed self-map of the disk. A fundamental problem is to relate properties of a composition operator to the function-theoretic properties of the self-map. During the recent decades these operators have been very actively studied in connection with various function spaces. The study of composition operators lies in the intersection of two central fields of mathematical analysis; function theory and operator theory. This thesis consists of four research articles and an overview. In the first three articles the weak compactness of composition operators is studied on certain vector-valued function spaces. A vector-valued function takes its values in some complex Banach space. In the first and third article sufficient conditions are given for a composition operator to be weakly compact on different versions of vector-valued BMOA spaces. In the second article characterizations are given for the weak compactness of a composition operator on harmonic Hardy spaces and spaces of Cauchy transforms, provided the functions take values in a reflexive Banach space. Composition operators are also considered on certain weak versions of the above function spaces. In addition, the relationship of different vector-valued function spaces is analyzed. In the fourth article weighted composition operators are studied on the scalar-valued BMOA space and its subspace VMOA. A weighted composition operator is obtained by first applying a composition operator and then a pointwise multiplier. A complete characterization is given for the boundedness and compactness of a weighted composition operator on BMOA and VMOA. Moreover, the essential norm of a weighted composition operator on VMOA is estimated. These results generalize many previously known results about composition operators and pointwise multipliers on these spaces.

Aspects of atomic decompositions and Bergman projections

The concept of an atomic decomposition was introduced by Coifman and Rochberg (1980) for weighted Bergman spaces on the unit disk. By the Riemann mapping theorem, functions in every simply connected domain in the complex plane have an atomic decomposition. However, a decomposition resulting from a conformal mapping of the unit disk tends to be very implicit and often lacks a clear connection to the geometry of the domain that it has been mapped into. The lattice of points, where the atoms of the decomposition are evaluated, usually follows the geometry of the original domain, but after mapping the domain into another this connection is easily lost and the layout of points becomes seemingly random. In the first article we construct an atomic decomposition directly on a weighted Bergman space on a class of regulated, simply connected domains. The construction uses the geometric properties of the regulated domain, but does not explicitly involve any conformal Riemann map from the unit disk. It is known that the Bergman projection is not bounded on the space L-infinity of bounded measurable functions. Taskinen (2004) introduced the locally convex spaces LV-infinity consisting of measurable and HV-infinity of analytic functions on the unit disk with the latter being a closed subspace of the former. They have the property that the Bergman projection is continuous from LV-infinity onto HV-infinity and, in some sense, the space HV-infinity is the smallest possible substitute to the space H-infinity of analytic functions. In the second article we extend the above result to a smoothly bounded strictly pseudoconvex domain. Here the related reproducing kernels are usually not known explicitly, and thus the proof of continuity of the Bergman projection is based on generalised Forelli-Rudin estimates instead of integral representations. The minimality of the space LV-infinity is shown by using peaking functions first constructed by Bell (1981). Taskinen (2003) showed that on the unit disk the space HV-infinity admits an atomic decomposition. This result is generalised in the third article by constructing an atomic decomposition for the space HV-infinity on a smoothly bounded strictly pseudoconvex domain. In this case every function can be presented as a linear combination of atoms such that the coefficient sequence belongs to a suitable Köthe co-echelon space.

Numerical integration over arbitrary polygonal domains based on Schwarz-Christoffel conformal mapping

This paper presents a new numerical integration technique oil arbitrary polygonal domains. The polygonal domain is mapped conformally to the unit disk using Schwarz-Christoffel mapping and a midpoint quadrature rule defined oil this unit disk is used. This method eliminates the need for a two-level isoparametric mapping Usually required. Moreover, the positivity of the Jacobian is guaranteed. Numerical results presented for a few benchmark problems in the context of polygonal finite elements show that the proposed method yields accurate results.

Coherence of the real symmetric Hardy algebra

Let D denote the open unit disk in C centered at 0. Let H-R(infinity) denote the set of all bounded and holomorphic functions defined in D that also satisfy f(z) = <(f <(z)over bar>)over bar> for all z is an element of D. It is shown that H-R(infinity) is a coherent ring.

Totally geodesic discs in strongly convex domains

We prove that every isometry from the unit disk Delta in , endowed with the Poincar, distance, to a strongly convex bounded domain Omega of class in , endowed with the Kobayashi distance, is the composition of a complex geodesic of Omega with either a conformal or an anti-conformal automorphism of Delta. As a corollary we obtain that every isometry for the Kobayashi distance, from a strongly convex bounded domain of class in to a strongly convex bounded domain of class in , is either holomorphic or anti-holomorphic.

Croissance des fonctions propres du laplacien sur un domaine circulaire

Ce mémoire a pour but d'étudier les propriétés des solutions à l'équation aux valeurs propres de l'opérateur de Laplace sur le disque lorsque les valeurs propres tendent vers l'in ni. En particulier, on s'intéresse au taux de croissance des normes ponctuelle et L1. Soit D le disque unitaire et @D sa frontière (le cercle unitaire). On s'inté- resse aux solutions de l'équation aux valeurs propres f = f avec soit des conditions frontières de Dirichlet (fj@D = 0), soit des conditions frontières de Neumann ( @f @nj@D = 0 ; notons que sur le disque, la dérivée normale est simplement la dérivée par rapport à la variable radiale : @ @n = @ @r ). Les fonctions propres correspondantes sont données par : f (r; ) = fn;m(r; ) = Jn(kn;mr)(Acos(n ) + B sin(n )) (Dirichlet) fN (r; ) = fN n;m(r; ) = Jn(k0 n;mr)(Acos(n ) + B sin(n )) (Neumann) où Jn est la fonction de Bessel de premier type d'ordre n, kn;m est son m- ième zéro et k0 n;m est le m-ième zéro de sa dérivée (ici on dénote les fonctions propres pour le problème de Dirichlet par f et celles pour le problème de Neumann par fN). Dans ce cas, on obtient que le spectre SpD( ) du laplacien sur D, c'est-à-dire l'ensemble de ses valeurs propres, est donné par : SpD( ) = f : f = fg = fk2 n;m : n = 0; 1; 2; : : :m = 1; 2; : : :g (Dirichlet) SpN D( ) = f : fN = fNg = fk0 n;m 2 : n = 0; 1; 2; : : :m = 1; 2; : : :g (Neumann) En n, on impose que nos fonctions propres soient normalisées par rapport à la norme L2 sur D, c'est-à-dire : R D F2 da = 1 (à partir de maintenant on utilise F pour noter les fonctions propres normalisées et f pour les fonctions propres quelconques). Sous ces conditions, on s'intéresse à déterminer le taux de croissance de la norme L1 des fonctions propres normalisées, notée jjF jj1, selon . Il est vi important de mentionner que la norme L1 d'une fonction sur un domaine correspond au maximum de sa valeur absolue sur le domaine. Notons que dépend de deux paramètres, m et n et que la dépendance entre et la norme L1 dépendra du rapport entre leurs taux de croissance. L'étude du comportement de la norme L1 est étroitement liée à l'étude de l'ensemble E(D) qui est l'ensemble des points d'accumulation de log(jjF jj1)= log : Notre principal résultat sera de montrer que [7=36; 1=4] E(B2) [1=18; 1=4]: Le mémoire est organisé comme suit. L'introdution et les résultats principaux sont présentés au chapitre 1. Au chapitre 2, on rappelle quelques faits biens connus concernant les fonctions propres du laplacien sur le disque et sur les fonctions de Bessel. Au chapitre 3, on prouve des résultats concernant la croissance de la norme ponctuelle des fonctions propres. On montre notamment que, si m=n ! 0, alors pour tout point donné (r; ) du disque, la valeur de F (r; ) décroit exponentiellement lorsque ! 1. Au chapitre 4, on montre plusieurs résultats sur la croissance de la norme L1. Le probl ème avec conditions frontières de Neumann est discuté au chapitre 5 et on présente quelques résultats numériques au chapitre 6. Une brève discussion et un sommaire de notre travail se trouve au chapitre 7.